Från Googlehemsida

Hoppa till: navigering, sök

Denna sida sammanfattar lite vad man lär sig på Algoritmer, datastrukturer och komplexitet (ADK) på KTH.

Innehåll

[redigera] P

I P finns problem som kan lösas i polynomisk tid.

[redigera] NP

Problem som kan verifieras i polynomisk tid.

Om NP = P vet ingen. Men man tror att NP != P.

Tes: Varje NP-fullständigt problem tar exponentiell tid att lösa i värsta fallet.

[redigera] NP-fullständigt

  1. Q finns i NP
  2. Q' kan reduceras till Q för alla Q' i NP

Om problemet endast uppfyller 2. så är problemet NP-svårt.

NP-fullständiga problem är dem svåraste problemen i NP. Varje problem i NP kan reduceras till varje NP-fullständigt problem. Den reduktionen tar polynomisk tid.

[redigera] NP-Svårt

Ett NP-svårt problem är ett problem som kan reduceras till ett NP-fullständigt problem men som inte kan verifieras i polynomisk tid

[redigera] Karp

Ett problem Q kan reduceras till Q'. Detta gör med fördel om vi har en lösning till Q'. Vi reducerar ett kännt NP-problem till vårat problem för att visa att vårat problem är minst lika svårt. Q är lättare eller lika svårt som Q', Man kan inte använda en lätt lösning till ett svårt problem. Därför kan inte lösningen till Q' vara lättare än lösningen till Q. Q' är ett svårare problem än (eller lika svårt som) Q.

Man reducerar inte för att det ska bli lättare, man reducerar för att man redan har en lösning till ett annat problem.