Forum: Offtopic Ist es endlich soweit? P != NP - Ein möglicher Beweis


von D. I. (Gast)


Lesenswert?


von Purzel H. (hacky)


Lesenswert?

Koennt schon sein ... die Natur arbeitet ja auch mit stochastischen 
Algorithmen. Was ist die Genetik anderes wie ein stochastischer 
Algorithmus ? Das waer die Antwort - was war die Frage ?

von Yalu X. (yalu) (Moderator)


Lesenswert?

Vorsicht: Der Satz

  "Sie [die nichtdeterministische Turing-Maschine] entscheidet sich bei
  jedem Rechenschritt zufällig für einen von mehreren möglichen Wegen,
  die Berechnung fortzusetzen;"

ist nicht richtig. Die NTM entscheidet sich nicht zufällig für einen der
möglichen Wege, sondern führt, bildlich gesprochen, alle möglichen Wege
parallel aus. Deswegen gibt es Probleme, die eine NTM in polynomieller
Zeit lösen kann, für die der beste bisher gefundene DTM-Algorithmus aber
exponentielle Zeit braucht.

Bisher war allerdings nicht klar, ob die gefundenen DTM-Algorithmen
wirklich die besten sind, oder die genannten Probleme vielleicht auch
von einer nichtparallelisierenden DTM in polynomieller Zeit gelöst
werden können. Das hätte bedeutet, dass die NTM bei dieser Klasse von
Problemen (auch NP-vollständige Probleme genannt) keinen Vorteil
gegenüber der DTM hätte. Hätte man für ein einziges NP-vollständiges
Problem einen Algorithmus gefunden, der auf einer DTM (und damit auch
auf einem realen Computer) in polynomieller Zeit abläuft, hätte man auf
einen Schlag auch für alle anderen bewiesenermaßen NP-vollständigen
Probleme Algorithmen mit dieser Eigenschaft konstruieren können. Damit
wären alle Probleme in NP auch in P, so dass NP=P wäre.

Nach den neuesten Erkenntnissen scheint dies aber nicht der Fall zu
sein. Wenn der Beweis stimmt, müssen uns also damit abfinden, dass die
NP-vollständigen Probleme auf einem realen Computer auch in Zukunft nur
in exponentieller Zeit gelöst werden können.

Ha-jetzt Aber schrieb:
> die Natur arbeitet ja auch mit stochastischen Algorithmen.

Aus den ganannten Gründen hat eine NTM nichts mit stochastischen
Algorithmen zu tun. Letztere lassen sich auch auf einem realen Computer
ausführen, bringen aber nicht die gewünschte Komplexitätsverringerung
von exponentiell nach polynomiell.

von D. I. (Gast)


Lesenswert?

Ja diese Fakten sind mir noch aus meiner Theoretischen Informatik 
Vorlesung bekannt.
Hehe ich stelle mir gerade das Szenario vor, was er wohl getan hätte 
wenn er einen Algorithmus für NP=P gefunden hätte. Ich hätte da wohl mit 
einer Veröffentlichung gewartet und wäre erstmal groß mit Online Banking 
einkaufen gegangen :D

von Läubi .. (laeubi) Benutzerseite


Lesenswert?

Yalu X. schrieb:
> Die NTM entscheidet sich nicht zufällig für einen der
> möglichen Wege, sondern führt, bildlich gesprochen, alle möglichen Wege
> parallel aus.
Sie entscheidt sich immer für den richtigen Weg, dann braucht man 
garnicht alle Wege folgen ;)

D. I. schrieb:
> Ich hätte da wohl mit
> einer Veröffentlichung gewartet
Ich hätte dem Algorithmus einen völlig wirren, langen, fast 
unausprechlichen Namen verpasst den fortan alle Studenten auswendig 
lernen müßten ;P

von Yalu X. (yalu) (Moderator)


Lesenswert?

Läubi .. schrieb:
>> Die NTM entscheidet sich nicht zufällig für einen der
>> möglichen Wege, sondern führt, bildlich gesprochen, alle möglichen Wege
>> parallel aus.
> Sie entscheidt sich immer für den richtigen Weg, dann braucht man
> garnicht alle Wege folgen ;)

Oder so, das ist eine Interpretationsfrage. In einer laufenden NTM
nachschauen, wie sie es wirklich macht, kann man sowieso nicht :)

Wenn man schreibt, sie entscheidet sich immer für den richtigen Weg,
muss man aber noch weitere Erläuterungen zur Funktionsweise mitliefern,
sonst könnte jemand auf die Idee kommen, die NTM löse jedes Problem in
O(1), weil sie ja vom Start weg gleich einen Weg einschlagen könnte, der
nichts anderes tut, als die richtige Lösung auszugeben (ohne weitere
Prüfung). Auch die Abgrenzung zur Orakel-Turingmaschine fällt so etwas
schwerer.

Da ist die Erklärung mit den parallel ausgeführten Lösungswegen in
meinen Augen etwas eingängiger.

von Falk B. (falk)


Lesenswert?

42

von Simon K. (simon) Benutzerseite


Lesenswert?

Worum geht es eigentlich? ;-) Verstehe kein Wort.

von Winfried J. (Firma: Nisch-Aufzüge) (winne) Benutzerseite


Lesenswert?

um hypothetische virtueller Mschinen zu Analyse nichtlinearer Prozesse?

von Frank B. (f-baer)


Lesenswert?

>Worum geht es eigentlich? ;-) Verstehe kein Wort.

Um die Frage, ob prinzipiell alle Probleme beliebiger Komplexität durch 
einen deterministischen Algorithmus in endlicher Zeit lösbar sind, also 
ohne Rückgriff auf Wahrscheinlichkeitsaussagen.

von D. I. (Gast)


Lesenswert?

"
Brief Bio

Born in 1971 in New Delhi, India.   Married with two children.  Other 
interests include historical and religious aspects of Hindu Dharma. 
Indian citizen.
"

Wenn er Glück hat und die schnell genug mit dem überprüfen sind, dürfte 
er auch noch eine Fields-Medaille erhalten da er noch unter 40 ist.

Interessant ist auch dass er mit 2 Kindern verheiratet ist ;) :D

von Arc N. (arc)


Lesenswert?

Frank Bär schrieb:
>>Worum geht es eigentlich? ;-) Verstehe kein Wort.
>
> Um die Frage, ob prinzipiell alle Probleme beliebiger Komplexität durch
> einen deterministischen Algorithmus in endlicher Zeit lösbar sind, also
> ohne Rückgriff auf Wahrscheinlichkeitsaussagen.

Jein, vorweg: der Begriff Nicht-Deterministische Turingmaschine ist u.U. 
etwas missverständlich...
NDTMs sind Turing-Maschinen die, je nach Ansatz, entweder alle möglichen 
Rechenpfade gleichzeitig ausführen oder mit einem sogenannten "luckiest 
possible guesser" immer den richtigen Pfad auswählen.
D.h. wann (in etwa) eine Aussage kommt ist determiniert, nur nicht der 
Weg dorthin.
Zu NP und P:
NP ist die Klasse aller Entscheidungsprobleme die eine NDTM in 
Polynomialzeit endscheiden kann.
P die Klasse, die eine normale, deterministische TM in Polynomialzeit 
entscheiden kann.
Die Frage war bzw. ist ob diese Klassen identisch sind, nicht ob es 
"schwerere" Aufgaben gibt. Solche Aufgaben gibt es, die zugehörigen 
Komplexitätsklassen sind bspw. PSPACE, EXPTIME oder NEXPTIME (letztere 
sind haben Laufzeiten von O(2^P(n). P(n) = Polynom)

von Yalu X. (yalu) (Moderator)


Lesenswert?

Simon K. schrieb:
> Worum geht es eigentlich? ;-) Verstehe kein Wort.

Salopp gesagt geht es um die Frage, ob für eine bestimmte, wichtige
Klasse von Problemen (nämlich der der NP-vollständigen Probleme)
Lösungsalgorithmen existieren, deren Zeitaufwand weniger als exponen-
tiell mit der Größe des Problems wächst.

Ein Beispiel eines NP-vollständigen Problems hängt mit dem 15er-Spiel
zusammen, das wohl jeder kennen dürfte:

  http://de.wikipedia.org/wiki/15-Puzzle

Die "Größe" des Problems wird in diesem Fall durch die Erhöhung der
Anzahl der Felder bestimmt, die nach Belieben erhöht werden kann

Die Aufgabe, die (einige) Informatiker interessiert ist es, einen mög-
lichst effizienten Algorithmus zu finden, der bei beliebiger Vermischung
der einzelnen Felder die kürzeste Zugfolge liefert, die die Felder
wieder in die sortierte Reihenfolge bringt.

Alle bekannten Algorithmen basieren im Prinzip darauf, dass erst einmal
alle Möglichkeiten für den ersten Zug ermittelt werden, für jeden dieser
Züge alle Möglichkeiten für den zweiten Zug usw. Da in jeder Situation 2
bis 4 Züge möglich sind, liegt die Anzahl der Zugfolgen aus k Zügen im
Bereich von 2^k bis 4^k. Da bei n Feldern die kürzeste Zugfolge bei
guter Mischung aus mindestens die Länge n hat (jedes Feld wird mindes-
tens einmal verschoben), wächst die Anzahl der Rechenschritte, die der
Algorithmus zur Lösung braucht, exponentiell mit der Anzahl der Felder.
Man kann zwar die Anzahl der zu untersuchenden Zugfolgen drastisch
reduzieren, aber die exponentielle Abhängigkeit bleibt.

Die Frage ist nun, ob es einen Algorithmus gibt, der dieses Problem in
polynomieller Zeit löst, so dass die Anzahl der Rechenschritte nur in
der m-ten Potenz mit der Anzahl der Felder wächst. Bisher hat noch
niemend einen gefunden, allerdings auch nicht bewiesen, dass es keinen
solchen Algorithmus gibt.

Es gibt noch viele weitere solcher Probleme, die in exponentieller Zeit
lösbar sind, wo man aber nicht wusste, ob es nicht vielleicht auch einen
polynomiellen Algorithmus gibt. Dazu zählen auch bedeutsamere Probleme
wie das Knacken verschlüsselter Nachrichten ohne Kenntnis des geheimen
Schlüssels.

All diese Probleme fasst man unter dem Begriff "NP-vollständig"
zusammen. Zur formalen Definition der NP-Vollständigkeit werden zwei
abstrakte Maschinen zur Ausführung von Algorithmen, nämlich die determi-
nistische und die nichtdeterministische Turing-Maschine herangezogen.

Herr Deolalikar will nun bewiesen haben, dass die NP-vollständigen
Probleme auf einer deterministischen Turing-Maschine (die von den
Fähigkeiten her einem realen Computer mit unendlich viel Speicher
entspricht) nicht in polynomieller Zeit lösbar sind. Das ist zwar
schon lange vermutet worden, aber nun ist es amtlich, sofern der Beweis
keine Fehler enthält.

von Simon K. (simon) Benutzerseite


Lesenswert?

Danke für die Erklärungen. Ich bin froh, dass wenigstens ihr das 
versteht :-)

Frank Bär schrieb:
> Um die Frage, ob prinzipiell alle Probleme beliebiger Komplexität durch
> einen deterministischen Algorithmus in endlicher Zeit lösbar sind, also
> ohne Rückgriff auf Wahrscheinlichkeitsaussagen.

Das hört sich eher nach einem philosophischen Problem an :-D

von Falk B. (falk)


Lesenswert?

@  Simon K. (simon) Benutzerseite

>Das hört sich eher nach einem philosophischen Problem an :-D

Eben, klingt wie die Suche nach der Weltformel, Stein der Weisen, 42.

Mal ganz pragmatisch-ingenieurtechnisch.

Nö, geht nicht, ist aber auch egal.

;-)

von D. I. (Gast)


Lesenswert?

Simon K. schrieb:
> Danke für die Erklärungen. Ich bin froh, dass wenigstens ihr das
> versteht :-)
>
> Frank Bär schrieb:
>> Um die Frage, ob prinzipiell alle Probleme beliebiger Komplexität durch
>> einen deterministischen Algorithmus in endlicher Zeit lösbar sind, also
>> ohne Rückgriff auf Wahrscheinlichkeitsaussagen.
>
> Das hört sich eher nach einem philosophischen Problem an :-D

Nur das ist es in dem Fall ganz und garnicht. Wäre P=NP, hätte das 
weitreichende Folgen für unser heutiges Leben, im Positiven könnten 
viele Optimierungsprobleme nun optimal gelöst werden und damit in 
verschiedenen Lebensbereichen die Qualität verbessert und Kosten gespart 
werden, als auch im Negativen, da damit die Kryptographie die uns bis 
heute bekannt ist hinfällig wäre in puncto Sicherheit. Es wäre vorerst 
kein sicheres Online-Banking usw. mehr möglich.

von Falk B. (falk)


Lesenswert?

@  D. I. (grotesque)

>> Das hört sich eher nach einem philosophischen Problem an :-D

>Nur das ist es in dem Fall ganz und garnicht.

Ich denke schon.

> Wäre P=NP, hätte das
>weitreichende Folgen für unser heutiges Leben,

Wirklich? Glaub ich nicht. Der Beweis spuckt ja nicht direkt die Lösung 
für alle komplexen Probleme aus, er sagt nur, dass sie existieren, wenn 
er denn positiv verlaufen wäre. Was aber IMO schon der "gesunde 
Menschenverstand" negativ entscheidet.

Allein die Formulierung, "beliebig komplexe Probleme in endlicher Zeit", 
"immer zufällig den richtigen Lösungsschritt" etc. ist schon arg 
abgespaced. Vielleicht sollten die Jungs ab und an mal wieder in die 
Realität eintauchen, und sich nicht nur in N-dimensionalen Räumen 
bewegen. N-> 00
Das klingt so wie ein allwissender Gott, der schnurstrackt den richtigen 
Lösungsweg geht, weil der die Lösung VORHER kennt.

> im Positiven könnten
>viele Optimierungsprobleme nun optimal gelöst werden und damit in
>verschiedenen Lebensbereichen die Qualität verbessert und Kosten gespart
>werden,

Jaja, klingt wie der Traum der kostenlosen, unbegrenzten Atomkraft in 
den 50er Jahren. Die Realität ist anders. Gott sei Dank ;-)

> als auch im Negativen, da damit die Kryptographie die uns bis
>heute bekannt ist hinfällig wäre in puncto Sicherheit. Es wäre vorerst
>kein sicheres Online-Banking usw. mehr möglich.

Der Knackpunkt von OnlineBanking liegt meist auf der menschlichen Seite, 
selten auf der technischen.

MfG
Falk

von D. I. (Gast)


Lesenswert?

Naja ein Beweis für P=NP hätte ja sein können dass er einfach einen 
Algorithmus angibt der z.B. TSP in polynomieller Zeit löst. Sache 
gegessen.

von Yalu X. (yalu) (Moderator)


Lesenswert?

Simon K. schrieb:
>> Um die Frage, ob prinzipiell alle Probleme beliebiger Komplexität durch
>> einen deterministischen Algorithmus in endlicher Zeit lösbar sind, also
>> ohne Rückgriff auf Wahrscheinlichkeitsaussagen.
>
> Das hört sich eher nach einem philosophischen Problem an :-D

Das hört sich nur deswegen philosophisch an, weil von einigen Vorpostern
ein paar Dinge durcheinandergebracht worden sind. Es geht bei dieser
Fragestellung weder um Probleme beliebiger Komplexität noch um Algorith-
men, die nicht in endlicher Zeit ausführbar sind noch um Wahrscheinlich-
keiten und zufallsgesteuerte Algorithmen.

Vielmehr betrifft der Satz ganz konkrete Algorithmen, wie sie in Logis-
tik- und Schachprogrammen, Autoroutern von Platinenlayoutprogrammen,
FPGA-Synthesetools und Optimierern in Compilern zu finden sind bzw. zu
finden wären, wenn man sie effizient implementieren könnte. Das sind
alles Programme mit denen jeder von uns schon einmal direkt oder indi-
rekt in Berührung gekommen ist.

Im Vergleich dazu erscheint bspw. die Quantentheorie um Größenordnungen
abgespaceter, weil sie wirklich jeglichem gesunden Menschenverstand
widerspricht. Aber auch sie hat gerade in der Elektronik ihren festen
Stellenwert, weil viele Phänomene, die sich in elektronischen Bauteilen
abspielen, nur durch sie erklärbar sind.

Falk Brunner schrieb:
>> Wäre P=NP, hätte das
>>weitreichende Folgen für unser heutiges Leben,
>
> Wirklich? Glaub ich nicht. Der Beweis spuckt ja nicht direkt die Lösung
> für alle komplexen Probleme aus, er sagt nur, dass sie existieren, wenn
> er denn positiv verlaufen wäre.

Na, na, woher willst du das denn wissen, wo es den Beweis doch gar nicht
gibt?

Es gibt schließlich auch konstruktive Beweise. In diesem Fall wäre ein
konstruktiver Beweis die Beschreibung eines Algorithmus, der ein einzi-
ges NP-vollständiges Probleme in polynomieller Zeit löst. Da aber die
meisten Beweise der NP-Vollständigkeit von Problemen darauf beruhen,
diese in bereits analysierte andere Probleme überzuführen, ließen sich
aus dem gefundenen Algorithmus sofort effiziente Algorithmen für eine
ganze Reihe weiterer Probleme ableiten.

Es würde also eine regelrechte Lawine ausgelöst werden, in deren Folge
ein nicht zu unterschätzender Teil der aktuellen Software als völlig
überholt gelten würde und neu geschrieben werden müsste, um konkurrenz-
fähig zu bleiben.

Wenn der Beweis von Deolalikar korrekt ist, wird dies natürlich nicht
passieren. Und auch wenn dieser Beweis nur eine lange gehegte Vermutung
bestätigt, hat er doch einen Nutzen: Die Kryptologen müssen nicht mehr
befürchten, dass irgendwann von einem Tag auf den anderen ihre Ver-
schlüsselungsverfahren nutzlos werden, weil sie von einem unerwartet
effizienten Algorithmus geknackt werden. Die Verschlüsselungsverfahren
werden jetzt nur noch durch die Steigerung der Rechenleistung von
Computern gefährdet, die aber — zumindest bisher — dank dem Mooreschen
Gesetz ziemlich gut vorhersehbar ist.

> Der Knackpunkt von OnlineBanking liegt meist auf der menschlichen
> Seite, selten auf der technischen.

Das liegt daran, dass gerade der Mensch ein hochgradig nichtdeterminis-
tisches System ist ;-)

von Läubi .. (laeubi) Benutzerseite


Lesenswert?

D. I. schrieb:
> Naja ein Beweis für P=NP hätte ja sein können dass er einfach einen
> Algorithmus angibt der z.B. TSP in polynomieller Zeit löst. Sache
> gegessen.
Wo sich einem die Hirnwindungen verdrehen ist finde ich eben erst wenn 
man einen Beweis angibt der zweifelsfrei festlegt das es eine Optimale 
Lösung/Strategie gibt aber trotzdem den Lösungsweg nicht kennt.

Wir hatten das mal in einer Vorlesung zur Automaten/Spieltheorie das 
Schokoladenspile (http://www.armin-p-barth.ch/pdf/3-4-0.pdf Seite 15 
Aufgabe 2).

Auf Seite 17 steht folgender Satz:
1
Jedes Zwei-Personen-Spiel, das die folgenden Eigenschaften 1 – 5 erfüllt, besitzt eine Gewinnstrategie für den einen oder anderen Spieler.
2
1) Die beiden Spieler A, B machen immer abwechselnd einen Zug. A beginnt.
3
2) Es gibt genau zwei mögliche Ausgänge des Spiels: A gewinnt oder B gewinnt.
4
3) Jeder Zug entsteht als eine Wahl des Spielers aus einer Menge möglicher Züge.
5
4) Zu jedem Zeitpunkt haben beide Spieler volle Kenntnis über die bisher gespiel-ten Züge und die weiteren möglichen Spielzüge.
6
5) Die Anzahl möglicher Züge ist von oben beschränkt.
Im folgendem wird dieser Satz bewiesen mit vollständiger Induktion. Da 
unser Spiel die Vorraussetzungen erfüllt wissen wir das es eine 
Gewinnstrategie entweder für A oder für B gibt, d.h. wenn derjenige 
"richtig" spielt kann er nicht verlieren egal was der andere tut.
Trotzdem wissen wir nicht wie diese Strategie aussieht!

von Falk B. (falk)


Lesenswert?

@  Yalu X. (yalu) (Moderator)

>> Wirklich? Glaub ich nicht. Der Beweis spuckt ja nicht direkt die Lösung
>> für alle komplexen Probleme aus, er sagt nur, dass sie existieren, wenn
>> er denn positiv verlaufen wäre.

>Na, na, woher willst du das denn wissen, wo es den Beweis doch gar nicht
>gibt?

Sagt mir mein Instinkt. Denn das wäre sowas wie ein 
informationstheoretisches schwarzes Loch, dass aus dem Nichts entsteht 
und plötzlich alles umsich herum aufsaugt. Das wird (hoffentlich) nicht 
so schnell passieren.

>diese in bereits analysierte andere Probleme überzuführen, ließen sich
>aus dem gefundenen Algorithmus sofort effiziente Algorithmen für eine
>ganze Reihe weiterer Probleme ableiten.

Keine Ahnung. Das übersteigt mein rudimentäres mathematisches 
Verständnis um Größenordungen.

>Es würde also eine regelrechte Lawine ausgelöst werden, in deren Folge
>ein nicht zu unterschätzender Teil der aktuellen Software als völlig
>überholt gelten würde und neu geschrieben werden müsste, um konkurrenz-
>fähig zu bleiben.

Eben das meine ich.

>Das liegt daran, dass gerade der Mensch ein hochgradig nichtdeterminis-
>tisches System ist ;-)

Seine Determiniertheit basiert auf seinen humanoiden Insuffizienzen ;-)

MFG
Falk

von P. M. (o-o)


Lesenswert?

Falk Brunner schrieb:
> Sagt mir mein Instinkt.

Instinkt verhält sich zu Theoretischer Informatik ungefähr wie McDonalds 
zu einem Ernährungsberater.

von Falk B. (falk)


Lesenswert?

@  P. M. (o-o)

>> Sagt mir mein Instinkt.

>Instinkt verhält sich zu Theoretischer Informatik ungefähr wie McDonalds
>zu einem Ernährungsberater.

Stimmt! ;-)

Ich erhebe ja auch keinen akademischen Anspruch auf Korrektheit.

von Michael S. (Firma: www.das-labor.org) (laborsauron)


Lesenswert?

>d.h. wenn derjenige
>"richtig" spielt kann er nicht verlieren egal was der andere tut
und wenn beide "richtig" spielen entsteht ein schwarzes Loch. :-)

von Yalu X. (yalu) (Moderator)


Lesenswert?

Michael Sauron schrieb:
>>d.h. wenn derjenige
>>"richtig" spielt kann er nicht verlieren egal was der andere tut
> und wenn beide "richtig" spielen entsteht ein schwarzes Loch. :-)

Nee, dann hängt der Gewinn von von der Marke der Schokoladentafel ab:
Ist es eine Ritter Sport, gewinnt der zweite Spieler, bei fast allen
anderen Marken der erste.

(ohne Smiley)

von Purzel H. (hacky)


Lesenswert?

Quantentheorie ist gar nicht so abgespacet, wie es den Anschein hat. Es 
geht in erster Linie darum, dass sich Materie anders verhaelt sobald die 
Unterteilung bei Kloetzchen endet anstelle sich wie ein 
Kontinuum(Fluessigkeit) zu verhalten. Das Verhalten der Kloetzchen 
bestimmt dann auch wieder das Verhalten der Menge. Der Rest ist 
aufwendige Mathematik. Da muss man dann einfach durch.
Dasselbe Verhalten kann man beobachten wenn man Menschenmengen (oder 
Sozialmengen) untersucht und irgendwann beim Individuum endet. Das 
Verhalten des Individuums bestimmt auch das Verhalten der Menge.

von Andreas F. (aferber)


Lesenswert?

Ha-jetzt Aber schrieb:
> Das Verhalten der Kloetzchen
> bestimmt dann auch wieder das Verhalten der Menge. Der Rest ist
> aufwendige Mathematik. Da muss man dann einfach durch.

Allerdings gilt sowohl für Menschenmengen als auch für Quanten, dass das 
Ganze etwas anderes ist als die Summe seiner Teile.

Beispiel Menschenmenge: wenn jeder einzelne das für ihn individuell 
rational vernünftige tut, bedeutet das nicht unbedingt ein gutes 
Ergebnis für die Menge. Im brennenden Kino ist es für jeden einzelnen 
eine vernünftige Verhaltensweise, sich so schnell wie möglich zum 
Ausgang zu begeben. Machen das aber alle gleichzeitig, verstopft der 
Ausgang, es kommt zum Stau, wodurch es Tote geben kann, obwohl bei 
optimaler Koordination alle rausgekommen wären. 
http://de.wikipedia.org/wiki/Rationalit%C3%A4tenfalle

Beispiel Quanten: Supraleiter erster Art. Elektronen verbinden sich zu 
Cooper-Paaren, dadurch wird aus zwei Fermionen auf einmal ein Boson, für 
das das Pauli-Prinzip nicht mehr gilt. Durch Kombination zweier Teilchen 
ist etwas qualitativ völlig anderes herausgekommen.

Andreas

von Läubi .. (laeubi) Benutzerseite


Lesenswert?

Yalu X. schrieb:
> (ohne Smiley)
Hm.. war es nicht so das immer Spieler 1 gewinnt? Kann aber auch sein 
das wir eine leicht abgewandelte Variante hatten.

von Yalu X. (yalu) (Moderator)


Lesenswert?

Läubi .. schrieb:
> Hm.. war es nicht so das immer Spieler 1 gewinnt? Kann aber auch sein
> das wir eine leicht abgewandelte Variante hatten.

Ich hätte mal gesagt, dass jeder Spieler versucht, die Schokolade so zu
brechen, dass ein quadratisches Stück (bzw. eins mit gleich vielen
Zeilen wie Spalten) übrig bleibt. Dem Gegenspieler bleibt dann nichts
anderes übrig, als dieses Quadrat zu zerstören, so dass es ihm nicht
gelingen wird, im letzten Zug das Stück mit dem X zu hinterlassen, da
dieses ja ebenfalls quadratisch ist.

Der erste Spieler kann diese Strategie nur dann erfogreich umsetzen,
wenn die Schokoladentafel nicht schon zu Beginn quadratisch ist.

von Winfried J. (Firma: Nisch-Aufzüge) (winne) Benutzerseite


Lesenswert?

....
Wobei quadratisch sich auf die Aazahl der Stücke bezieht, nicht etwa auf 
die äußere Form der stücken oder der Tafel.

Wie würde das bei drei oder sechseckigen stücken ausgehen?

braucht es dann 3 Spieler?

von Paul B. (paul_baumann)


Lesenswert?

>Der erste Spieler kann diese Strategie nur dann erfogreich umsetzen,
>wenn die Schokoladentafel nicht schon zu Beginn quadratisch ist.

Wenn dieses Spiel in genügend vielen Durchgängen gespielt wurde, nehmen
die Körper der Spielenden auch eine quadratische Form an. Erst heute
wieder sah ich ein paar Schulkinder mit dem Format 80x80cm.
(Kopfkissenformat)

;-)
MfG Paul

von Yalu X. (yalu) (Moderator)


Lesenswert?

Winfried J. schrieb:
> Wie würde das bei drei oder sechseckigen stücken ausgehen?

Interessante Aufgabenerweiterung :) Hast du dafür schon eine Strategie
gefunden?

Ein Bisschen schwieriger wird die ursprünglich Aufgabe auch dann, wenn
das mit X gekennzeichnete Stück nicht in der Ecke der Tafel, sondern an
einer beliebigen Position auf der Tafel liegt.

Paul Baumann schrieb:
> Erst heute wieder sah ich ein paar Schulkinder mit dem Format 80x80cm.

Ja, das ist das typische Symptom übermäßigen Ritter-Sport-Genusses. Dem
kann nur durch regelmäßiges Einwerfen einer Toblerone-Stange (aber bitte
längs, nicht quer) entgegengewirkt werden. Das sollte aber auch nicht zu
oft passieren, sonst bekommen die Schüler mit der Zeit einen dreieckigen
Querschnitt, was auch nicht gut aussieht ;-)

Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.