Klasa Co-NPC

Wikipedia:Weryfikowalność
 Ten artykuł od 2020-12 wymaga zweryfikowania podanych informacji.
Należy podać wiarygodne źródła w formie przypisów bibliograficznych.
Część lub nawet wszystkie informacje w artykule mogą być nieprawdziwe. Jako pozbawione źródeł mogą zostać zakwestionowane i usunięte.
Sprawdź w źródłach: Encyklopedia PWN • Google Books • Google Scholar • Federacja Bibliotek Cyfrowych • BazHum • BazTech • RCIN • Internet Archive (texts / inlibrary)
Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu.

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.

  • p
  • d
  • e
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
  • Hierarchia wielomianowa
  • Hierarchia wykładnicza
  • Hierarchia Grzegorczyka
  • Hierarchia arytmetyczna
  • Hierarchia Boole'owska
Rodziny klas
  • DTIME
  • NTIME
  • DSPACE
  • NSPACE
  • Dowód weryfikowalny probabilistycznie
  • Interaktywny system dowodowy