P=NP?

Från Wikipedia

P=NP? är ett problem inom teoretisk datalogi och handlar om huruvida två klasser av beräkningsproblem, P och NP, är olika eller inte.

Problemet lyder:

• Finns det något beräkningsproblem som kan lösas av en icke-deterministisk turingmaskin i polynomiell tid, dvs det ligger i komplexitetsklassen NP, men inte av en deterministisk turingmaskin, dvs det ligger inte i komplexitetsklassen P?

Det anses allmänt att svaret är att P inte är lika med NP. En stor klass beräkningsproblem har visats vara NP-fullständiga. Ett problem är NP-fullständigt om det har egenskapen att om det finns en polynomiell deterministisk algoritm för problemet, så finns en polynomiell deterministisk algoritm för alla problem i NP.

Ett bevis för existensen av ett beräkningproblem som ligger i NP men inte i P skulle alltså innebära att inget NP-fullständigt problem ligger i P.