Co-NP-kompletní - Co-NP-complete

v teorie složitosti, výpočetní problémy, které jsou co-NP-kompletní jsou ty, ve kterých jsou nejtěžší problémy co-NP, v tom smyslu, že jakýkoli problém v co-NP lze přeformulovat jako speciální případ jakéhokoli problému co-NP-úplného s pouze polynomiální režií. Li P se liší od co-NP, pak všechny problémy co-NP-complete nejsou řešitelné v polynomiálním čase. Pokud existuje způsob, jak rychle vyřešit problém co-NP-kompletní, lze tento algoritmus použít k rychlému vyřešení všech problémů co-NP.

Každý co-NP-úplný problém je doplněk z NP-kompletní problém. V obou jsou určité problémy NP a co-NP, například všechny problémy v P nebo celočíselná faktorizace. Není však známo, zda jsou množiny stejné, i když nerovnost je považována za pravděpodobnější. Vidět co-NP a NP-kompletní Více podrobností.

Fortune v roce 1979 ukázalo, že pokud existuje řídký jazyk je tedy co-NP-kompletní (nebo dokonce jen co-NP-hard) P = NP,[1] kritický základ pro Mahaneyova věta.

Formální definice

A rozhodovací problém C je co-NP-kompletní, pokud je v co-NP a pokud je každý problém v co-NP polynomial-time many-one reducible k tomu.[2] To znamená, že pro každý problém co-NP L, existuje polynomiální časový algoritmus, který může transformovat jakoukoli instanci L do instance C se stejným pravdivostní hodnota. V důsledku toho, kdybychom měli polynomiální časový algoritmus pro C, mohli bychom vyřešit všechny problémy co-NP v polynomiálním čase.

Příklad

Jedním z příkladů úplného problému co-NP je tautologie, problém určení, zda daný Booleovský vzorec je tautologie; to znamená, že každé možné přiřazení hodnot true / false proměnným přinese pravdivé prohlášení. To úzce souvisí s Booleovský problém uspokojivosti, který se ptá, zda existuje aspoň jeden takové přiřazení a je NP-úplné.[2]

Reference

  1. ^ Fortune, S. (1979). „Poznámka k řídkým kompletním sadám“ (PDF). SIAM Journal on Computing. 8 (3): 431–433. doi:10.1137/0208034.
  2. ^ A b Arora, Sanjeev; Barak, Boaz (2009). Teorie složitosti: moderní přístup. Cambridge University Press. ISBN  978-0-521-42426-4.

externí odkazy