FP (komplexitet)

I beräkningskomplexitetsteori är komplexitetsklassen FP den uppsättning funktionsproblem som kan lösas av en deterministisk Turingmaskin i polynomtid . Det är funktionsproblemversionen av beslutsproblemklassen P . Grovt sett är det klassen av funktioner som effektivt kan beräknas på klassiska datorer utan randomisering.

Skillnaden mellan FP och P är att problem i P har enbits, ja/nej svar, medan problem i FP kan ha vilken utdata som helst som kan beräknas i polynomtid. Att lägga till två tal är till exempel ett FP- problem, medan bestämning av om deras summa är udda är i P .

Polynomtidsfunktionsproblem är grundläggande för att definiera polynomtidsreduktioner, som i sin tur används för att definiera klassen av NP-kompletta problem.

Formell definition

FP definieras formellt enligt följande:

En binär relation $P(x,y)$ finns i FP om och endast om det finns en deterministisk polynomtidsalgoritm som, givet $x$ , kan hitta någon $y$ så att $P(x,y)$ gäller.

Relaterade komplexitetsklasser

• FNP är den mängd binära relationer för vilka det finns en polynomtidsalgoritm som, givet x och y , kontrollerar om P( x , y ) håller. Precis som P och FP är nära besläktade, är NP nära besläktade med FNP . FP = FNP om och endast om P = NP .
• Eftersom en maskin som använder logaritmiskt utrymme har högst polynomiellt många konfigurationer, FL , uppsättningen funktionsproblem som kan beräknas i logrymden, finns i FP . Det är inte känt om FL = FP ; detta är analogt med problemet med att avgöra om beslutsklasserna P och L är lika.

externa länkar

• Komplexitet Zoo: FP