Diskussion:NP-Vollständigkeit/Archiv
Leichte Konstruktion nicht praxisrelevanter Beispiele?
Ist es wirklich wahr, dass sich leicht ein kaum praxisrelevantes NP-vollständiges Problem konstruieren läßt? Ich höre das hier zum ersten mal. Ich denke, auch eine Reduktion auf ein nicht praxisrelevantes Problem wäre einfacher gewesen als Cooks direkter Beweis. Ich bitte um Quellen oder Angabe der Konstruktion. --Tian 16:33, 12. Okt 2004 (CEST)
Ah, vielleicht war die Sprache der Paare (M,x) gemeint, wobei M die Kodierung einer standardisierten polynomialzeitbeschränkten nichtdeterministischen TM ist, die x akzeptiert. (Standardisiert bedeutet dabei in formalisierter Form, dass man die Polynomialzeitbeschränkung leicht nachprüfen kann.) Cook hat im wesentlichen diese Sprache auf SAT zurückgeführt, aber mir scheint, diese Sichtweise ist neuer. Cook hat meiner Meinung nach anders als es die Formulierung des Artikels nahelegt als erster gezeigt, dass es überhaupt NP-vollständige Probleme gibt. -- Tian 16:46, 28. Feb 2005 (CET)
- Ja, Cook hat als erster die Existenz gezeigt! Aber das ist ja häufig so, dass man einfachere Beweise erst später findet. --Coma 02:57, 1. Mär 2005 (CET)