Completo (complessità)

Nella teoria della complessità computazionale, un problema computazionale è completo per una classe di complessità se è, in senso tecnico, tra i problemi "più difficili" (o "più espressivi") di quella classe. In questo senso, esso è un rappresentante di quella classe. Si tratta di una nozione centrale per la complessità. Essa permette in particolare di stabilire inclusioni tra le classi considerando un solo problema.

Un problema p è detto difficile (in inglese hard) per una classe di complessità C per un dato tipo di riduzione, se esiste una riduzione (del tipo dato) da qualsiasi problema in C a p. Se un problema è difficile per quella classe e al tempo stesso appartiene ad essa, esso è completo per quella classe (per quel tipo di riduzione).

Un problema che è completo per una classe C si dice C-completo, e la classe di tutti i problemi completi per C è denominata C-completo. La prima classe completa a essere definita e la più nota è NP-completo, una classe che contiene molti problemi difficili da risolvere che sorgono nella pratica. Similmente, un problema difficile per una classe C è chiamato C-difficile, ad es. NP-difficile.

Normalmente si assume che la riduzione in questione non abbia una complessità computazionale superiore alla classe stessa. Perciò si può dire che se un problema C-completo ha una soluzione "computazionalmente facile", allora tutti i problemi in "C" hanno una soluzione "facile".

Il problema di soddisfacibilità booleana delle formule logiche (limitate a tre lettere) 3SAT è uno dei problemi completi classici della classe NP.

Per provare che una classe C è contenuta in una classe C', basta dimostrare che un problema C-completo appartiene alla classe C'. In particolare, se un problema è completo per due classi di complessità C e C', allora C = C'. Un esempio di questo principio è il teorema di Shamir, che stabilisce l'uguaglianza IP = PSPACE, dove IP è la classe dei problemi che possiedono una prova interattiva in tempo polinomiale.

Generalmente, le classi di complessità che hanno un'enumerazione ricorsiva hanno problemi completi conosciuti, mentre le altre no. Ad esempio, NP, co-NP, PLS e PPA hanno tutti problemi completi naturali conosciuti, mentre RP, ZPP, BPP e TFNP non hanno problemi completi conosciuti (almeno in base alle attuali conoscenze).

Ci sono classi senza problemi completi. Ad esempio, Sipser mostrò che esiste un linguaggio M tale che BPP^M (BPP con oracolo M) non ha problemi completi.^[1].

• (EN) Complexity Zoo Archiviato il 27 agosto 2019 in Internet Archive., un wiki dell'Università di Waterloo creata da Scott Aaronson, che cataloga tutte le classi di complessità computazionale

Portale Informatica

Portale Matematica