Co-NP-zupełność – klasa złożoności zawierająca takie problemy klasy Co-NP, że każdy inny problem klasy Co-NP może zostać do nich zredukowany, analogicznie jak dla problemów NP-zupełnych. Ponadto problem dopełniający względem problemu NP-zupełnego jest NP-trudny.
uważane
za wykonalne |
- DLOGTIME
- AC0
- ACC0
- TC0
- L
- SL
- RL
- NL
- NC
- SC
- CC
- P (P-zupełność)
- ZPP
- RP
- BPP
- BQP
- APX
|
|---|
podejrzewane
o niewykonalność |
- UP
- NP
- AM
- QMA
- PH
- ⊕P
- PP
- #P (#P-zupełność)
- IP
- PSPACE
- (PSPACE-zupełność)
|
|---|
uważane
za niewykonalne |
- EXPTIME
- NEXPTIME
- EXPSPACE
- ELEMENTARY
- PR
- R
- RE
- ALL
|
|---|
| hierarchie klas |
- wielomianowa
- wykładnicza
- Grzegorczyka
- arytmetyczna
- boolowska
|
|---|
| rodziny klas |
- DTIME
- NTIME
- DSPACE
- NSPACE
- Dowód weryfikowalny probabilistycznie
- Interaktywny system dowodowy
|
|---|