Потпуност (теорија рачунске сложености)

У математичкој теорији комплексности рачунски проблем је комплетан за сложености класе што је, у техничком смислу, међу "најтежим" проблемима у класи сложености.

Више формално, проблем p се зове тешким за сложености класе C под одређеним врстама смањења (комплексности), ако постоји смањење ( датог типа) из било ког проблема из C у p. Ако је проблем тежак за класу онда је и члан класе, комплетан за ту класу (за ту врсту редукције).

Проблем који је комплетан за класу C каже се да је C-комплетан, и класа свих проблема комплетних за C означава се са C -комплетан . Прва комплетна класа се дефинише и најпознатија је NP -комплетна класа, која садржи многе тешке проблеме који се могу решити и који се јављају у пракси. Слично томе, проблем тежине за класу C се зове C-тешко, нпр NP -тешких.

Обично се претпоставља да је у питању смањење које нема већу комплексност израчунавања од саме класе. Стога се може рећи да ако C -комплетан проблем има "рачунски лако" решење, онда сви проблеми у " C " имају "лако" решење.

Генерално, сложеност класа које имају рекурзивно пописивање да знају комплетне проблеме, док оне који немају, немају никакве познате комплетне проблеме. На пример, NP, co-NP, PLS PPA сви имају познате природне комплетне проблеме, док RP, ZPP, BPP и TFNP немају никакве познате комплетне проблеме (иако такав проблем може бити откривен у будућности).

Постоје класе без комплетних проблема. На пример, Sipser показује да постоји језик M и да BPP^M (BPP са пророчанством M) нема комплетних проблема.