e^ipi = -1 aus Simpsons

Gregor

1310-Logik schrieb:

P=NP

Stimmt das auch?

Ich bin da pessimistisch. ...aber wer weiß!?

Jester

Ich kenne ne ganze Menge Leute, die sich so richtig drüber ärgern würden. Da kopnstruiert man seit Jahren polynomiale Approximationsalgos für NP-vollständige Probleme und dann kommt irgendjemand daher und zeigt, daß das alles vollkommen unnötig war.

CStoll

1310-Logik schrieb:

In der selben Simpsons-Folge steht doch auch

P=NP

Stimmt das auch? Bitte mit Beweis

Ob das stimmt, ist bislang noch nicht bewiesen.
(aber die meisten Experten gehen heute davon aus, daß es nicht stimmt)

wolfgke

Wer sagt, dass es unnötig wäre, polynomiale Approximationen zu bestimmen auch wenn P!=NP?

Auf der Homepage des Clay Institutes (die, die unter anderem 1 Mio $ auf den Beweis von P=NP oder P!=NP bieten), wird in der Problembeschreibung ausdrücklich auf den Fall eingegangen, dass P!=NP sein könnte, jedoch aus irgendwelchen Gründen die in der Praxis auftretenden Instanzen von NP-vollständigen Problemen eine Eigenschaft besitzen könnten, trotzdem polynomiell lösbar zu sein (was dann jedoch da P!=NP dann wäre, nicht für alle zutrifft - klar). Und da lohnt es sich schon Arbeit hereinzustecken - unabhängig von der Relation zwischen P und NP.

P. S.: Ich werde solange glauben, dass P=NP ist, bis mir jemand das Gegenteil beweist und ich den Beweis verstanden habe. Schon allein aus Protest gegen die ganzen Leute, die überzeugt sind P != NP und die Mathematiker seien nur zu blöd das akkurat zu beweisen.

zu dieser für die menschheit doch enorm wichtigen frage fällt mir nur eins ein: wayne

Gregor

@wolfgke: Ist schwer zu verstehen, was Du sagen wolltest, da Du andauernd = und != verwechselst.

Gregor

you no take candle schrieb:

zu dieser für die menschheit doch enorm wichtigen frage fällt mir nur eins ein: wayne

In der Tat: Das ist eine enorm wichtige Frage. Wenn jemand P=NP zeigen könnte, am Besten noch mit einer Art konstruktivem Beweis, dann würde das die Computerlandschaft enorm verändern. Jeder, der sich mit Rechnern in einer Art auseinandersetzt, dass er in einem Forum wie diesem aktiv ist, sollte sehr an der Lösung dieses Problems interessiert sein.

zu P/NP:
Die Experten waren vor ein paar Jahren auch noch der Meinung, die Primzahleigenschaft sei nicht in polynomieller Zeit prüfbar.

Solche Einschätzungen sind imho Nullaussagen.

Jester

wolfgke schrieb:

Wer sagt, dass es unnötig wäre, polynomiale Approximationen zu bestimmen auch wenn P!=NP?

Niemand. Nur wenn P=NP wahr ist, dann sind die ganzen Algos nicht mehr so interessant. Logisch, oder?

CStoll

wolfgke schrieb:

Auf der Homepage des Clay Institutes (die, die unter anderem 1 Mio $ auf den Beweis von P=NP oder P!=NP bieten), wird in der Problembeschreibung ausdrücklich auf den Fall eingegangen, dass P!=NP sein könnte, jedoch aus irgendwelchen Gründen die in der Praxis auftretenden Instanzen von NP-vollständigen Problemen eine Eigenschaft besitzen könnten, trotzdem polynomiell lösbar zu sein (was dann jedoch da P!=NP dann wäre, nicht für alle zutrifft - klar). Und da lohnt es sich schon Arbeit hereinzustecken - unabhängig von der Relation zwischen P und NP.

Soviel ist sicher: Wenn irgendeines der bekannten NP-vollständigen Probleme eine Polynomialzeit-Lösung besitzt, dann kann daraus für alle Probleme in NP eine Lösung konstruiert werden (Stichwort: Polynomialzeit-Reduktion) - also wäre damit P=NP bewiesen.

(damit reicht es für den Nachweis "P=NP" aus, ein NP-vollständiges Problem in Poly-Zeit lösen zu können)

CStoll schrieb:

Soviel ist sicher: Wenn irgendeines der bekannten NP-vollständigen Probleme eine Polynomialzeit-Lösung besitzt, dann kann daraus für alle Probleme in NP eine Lösung konstruiert werden (Stichwort: Polynomialzeit-Reduktion) - also wäre damit P=NP bewiesen.

(damit reicht es für den Nachweis "P=NP" aus, ein NP-vollständiges Problem in Poly-Zeit lösen zu können)

es kann aber sein, dass in der praxis gewisse randbedingungen quasi ein anderes problem daraus machen...