Multiprozessorsysteme und klassische Komplexitätsprobleme

[Andre (Gast)]

Hallo an das Forum,

ich hätte mal eine Grundsatzfrage.

Ich würde gerne wissen, wie sich künftige Multiprozessorsystem, auf 
klassische Probleme aus Komplexitätstheorie auswirken (z.b polynomielle 
oder exponentielle Probleme)? Was denke ihr wie sich die Schranken 
verändern ??

Gruß Andre

[(prx) A. K. (prx)]

Andre schrieb:

> Ich würde gerne wissen, wie sich künftige Multiprozessorsystem, auf
> klassische Probleme aus Komplexitätstheorie auswirken (z.b polynomielle
> oder exponentielle Probleme)?

Ungefähr ab unendlich vieler paralleler Prozessoren wird sich 
substantiell etwas an der Theorie verändern. ;-)

[Student (Gast)]

GPUs haben schon viele hundert bis knapp über tausend kleine 
Rechenkerne.
Supercomputer haben mehrere hunderttausend Rechenkerne.

Alles schon jetzt verfügbar.

Das ändert an der Theorie aber nix ;-)

[klaus (Gast)]

Komplexitätsberechnungen werden immer anhand gewisser Rechnermodelle 
gemacht, typischerweise die detereministische Turingmaschine (= 
1-Kern-Prozessor), die nichtdeterministische Turingmaschine (= 
Prozessor, der alle Rechenwege gleichzeitig ausprobiert bzw. sich immer 
für den richtigen Rechenweg entscheidet) und dann noch Netzwerkmodelle, 
wo eine Anzahl Knoten über eine klar definierte Kommunikation (Message 
Passing oder Shared Memory) das Problem lösen. Die Theorie ist auch für 
Multiprozessorsysteme weitgehend untersucht und bekannt.

Theoretisch gesehen bringt ein Multiprozessorsystem bestenfalls einen 
Speed-up von n bei n Prozessoren, die Komplexität ändert sich also vom 
Ein- zum n-Kernsystem bestenfalls von O(x) nach O(x/n).

Tatsächlich verringert sich der Speed-up noch stark, da die Prozessoren 
kommunizieren und aufeinander warten müssen und gewisse Berechnungen 
nicht parallelisiert werden können.

[IGCT (Gast)]

Dabei fällt mir ein... P != NP

http://www.scribd.com/doc/35539144/pnp12pt Das wäre schon der Hammer 
wenns stimmen sollte...

[D. I. (Gast)]

IGCT schrieb:
> Dabei fällt mir ein... P != NP
>
> http://www.scribd.com/doc/35539144/pnp12pt Das wäre schon der Hammer
> wenns stimmen sollte...

Das ist doch nun schon ein alter Hut. Der Thread dazu findet sich hier 
etwas weiter hinten und es stimmt ziemlich wahrscheinlich. Ihr wisst 
doch nach dem Problem ist vor dem Problem und ein gelöstes ist immer 
leicht.

[Andreas F. (aferber)]

IGCT schrieb:
> Dabei fällt mir ein... P != NP
>
> http://www.scribd.com/doc/35539144/pnp12pt Das wäre schon der Hammer
> wenns stimmen sollte...

Sieht eher schlecht aus, war wohl nur ein Sturm im Wasserglas:

http://www.newscientist.com/article/dn19313-tide-turns-against-milliondollar-maths-proof.html

Andreas