Co-NP

În teoria complexității de calcul , $c sau Nu. P.$ ${\ displaystyle coNP}$ ${\ displaystyle coNP}$ este clasa problemelor complementare celor din clasă $Nu. P.$ ${\ displaystyle NP}$ $NP$ . Într-un mod mai formal, avem asta dacă $S.$ ${\ displaystyle S}$ $S.$ este o problemă la alfabet $LA$ ${\ displaystyle A}$ $LA$ atunci este o problemă de clasă $c sau Nu. P.$ ${\ displaystyle coNP}$ ${\ displaystyle coNP}$ dacă și numai dacă $A^{*}\backslash S=S^{c}$ ${\ displaystyle A ^ {*} \ backslash S = S ^ {c}}$ ${\ displaystyle A ^ {*} \ backslash S = S ^ {c}}$ este o problemă de clasă $Nu. P.$ ${\ displaystyle NP}$ $NP$ .

În ceea ce privește egalitatea $coNP=NP$ ${\ displaystyle coNP = NP}$ ${\ displaystyle coNP = NP}$ nu ne putem exprima.

Într-adevăr, pentru a vedea dacă unele de intrare $w\in A^{*}$ ${\ displaystyle w \ în A ^ {*}}$ ${\ displaystyle w \ în A ^ {*}}$ este de natură să fie de $S.$ ${\ displaystyle S}$ $S.$ sau să nu fie așa că ar trebui să așteptăm toate calculele posibile ale mașinii Turing nedeterministe pe care o acceptă $S^{c}$ ${\ displaystyle S ^ {c}}$ ${\ displaystyle S ^ {c}}$ urmează cursul lor; adică să fii sigur că $w\in S$ ${\ displaystyle w \ in S}$ $w \ in S$ nici un calcul nu ar trebui să se blocheze în timp ce dacă $w\not \in S$ ${\ displaystyle w \ not \ în S}$ ${\ displaystyle w \ not \ în S}$ atunci cel puțin unul dintre aceste calcule ar trebui să se oprească. Pentru a face acest lucru, totuși, nu se folosește un timp polinomial.

De aceea nu se poate spune nimic despre egalitate $c sau Nu. P.$ ${\ displaystyle coNP}$ ${\ displaystyle coNP}$ și $Nu. P.$ ${\ displaystyle NP}$ $NP$ .

Portal IT

Portalul de matematică