Potpunost (teorija računske složenosti)

U matematičkoj teoriji kompleksnosti računski problem je kompletan za složenosti klase što je, u tehničkom smislu, među "najtežim" problemima u klasi složenosti.

Više formalno, problem p se zove teškim za složenosti klase C pod određenim vrstama smanjenja (kompleksnosti), ako postoji smanjenje ( datog tipa) iz bilo kog problema iz C u p. Ako je problem težak za klasu onda je i član klase, kompletan za tu klasu (za tu vrstu redukcije).

Problem koji je kompletan za klasu C kaže se da je C-kompletan, i klasa svih problema kompletnih za C označava se sa C -kompletan . Prva kompletna klasa se definiše i najpoznatija je NP -kompletna klasa, koja sadrži mnoge teške probleme koji se mogu rešiti i koji se javljaju u praksi. Slično tome, problem težine za klasu C se zove C-teško, npr NP -teških.

Obično se pretpostavlja da je u pitanju smanjenje koje nema veću kompleksnost izračunavanja od same klase. Stoga se može reći da ako C -kompletan problem ima "računski lako" rešenje, onda svi problemi u " C " imaju "lako" rešenje.

Generalno, složenost klasa koje imaju rekurzivno popisivanje da znaju kompletne probleme, dok one koji nemaju, nemaju nikakve poznate kompletne probleme. Na primer, NP, co-NP, PLS PPA svi imaju poznate prirodne kompletne probleme, dok RP, ZPP, BPP i TFNP nemaju nikakve poznate kompletne probleme (iako takav problem može biti otkriven u budućnosti).

Postoje klase bez kompletnih problema. Na primer, Sipser pokazuje da postoji jezik M i da BPP^M (BPP sa proročanstvom M) nema kompletnih problema.