Löftesproblem

I beräkningskomplexitetsteori är ett löftesproblem en generalisering av ett beslutsproblem där indata lovas att tillhöra en viss delmängd av alla möjliga indata. Till skillnad från beslutsproblem tar ja- instanserna (ingångarna för vilka en algoritm måste returnera ja ) och nej- instanserna inte uppsättningen av alla indata. Intuitivt har algoritmen lovats att indata verkligen tillhör en uppsättning av ja- instanser eller nej- instanser. Det kan finnas ingångar som varken är ja eller nej . Om en sådan inmatning ges till en algoritm för att lösa ett löftesproblem, tillåts algoritmen att mata ut vad som helst, och kanske till och med inte stanna.

Formell definition

Ett beslutsproblem kan associeras med ett språk ${\displaystyle L\subseteq \{0,1\}^{*}} ,$ där problemet är att acceptera alla inmatningar i $L$ och avvisa alla ingångar som inte finns i $L$ . För ett löftesproblem finns det två språk, $L_{\text{YES}}$ och ${\displaystyle L_{\text{NO}}} ,$ som måste vara disjunkta , vilket betyder ${\displaystyle L_{\text{YES}}\cap L_{\text{NO}}=\varnothing } , så att alla$ ingångar i $L_{\text{YES}}$ ska accepteras och alla inmatningar i $L_{\text{NO}}$ ska avvisas. Mängden $L_{\text{YES}}\cup L_{\text{NO}}$ kallas löftet . Det finns inga krav på utgången om ingången inte hör till löftet. Om löftet är lika med $\{0,1\}^{*}$ , så är detta också ett beslutsproblem, och löftet sägs vara trivialt.

Exempel

Många naturliga problem är faktiskt löftesproblem. Tänk till exempel på följande problem: Givet en riktad acyklisk graf , bestäm om grafen har en bana med längden 10. Ja -instanserna är riktade acykliska grafer med en väg av längden 10, medan nej -instanserna är riktade acykliska grafer utan väg av längd 10. Löftet är uppsättningen riktade acykliska grafer. I det här exemplet är löftet lätt att kontrollera. I synnerhet är det mycket lätt att kontrollera om en given graf är cyklisk. Den utlovade egendomen kan dock vara svår att värdera. Tänk till exempel på problemet "Med tanke på en Hamiltonsk graf , avgör om grafen har en cykel av storlek 4." Nu är löftet NP-svårt att utvärdera, men löftesproblemet är lätt att lösa eftersom kontroll av cykler av storlek 4 kan göras i polynomtid.

Se även

Undersökningar

Goldreich, Oded (2006). "Om löftesproblem (en undersökning)" . Teoretisk datavetenskap: Uppsatser till minne av Shimon Even . LNCS . Vol. 3895. s. 254–290. doi : 10.1007/11685654_12 .
Sahai, A.; Vadhan, SP (1997). "Ett fullständigt löftesproblem för statistisk nollkunskap". FOCS 1997 . s. 448–457. CiteSeerX 10.1.1.34.6920 . doi : 10.1109/SFCS.1997.646133 .
Till och med, Shimon; Selman, Alan L .; Yacobi, Yacov (1984). "Komplexiteten i löftesproblem med applikationer för kryptografi med publik nyckel" . Information och kontroll . 61 (2): 159–173. doi : 10.1016/S0019-9958(84)80056-X .