Sharp-P-completo

#P-completo (pronunciato "sharp P completo" o, talvolta, "numero P completo" o "cancelletto P completo") è una classe di complessità nella teoria della complessità computazionale. Per definizione, un problema è #P-completo se e solo se è in #P, e ogni problema in #P può essere ridotto ad esso da una riduzione per conteggio in tempo polinomiale, ossia da una riduzione di Turing in tempo polinomiale relativa alle cardinalità degli insiemi delle soluzioni. In modo equivalente, un problema è #P-completo se e solo se è in #P, e per qualsiasi macchina di Turing non deterministica ("macchina NP"), il problema di computare il suo numero di cammini di accettazione può essere ridotto a questo problema.

Esempi di problemi di #P-completo includono:

Quante diverse assegnazioni variabili soddisferanno una data formula generale booleana? (#SAT)
Quante diverse assegnazioni variabili soddisferanno una data formula FND?
Quante diverse assegnazioni variabili soddisferanno una data formula 2SAT?
Quanti accoppiamenti perfetti ci sono per un dato grafo bipartito?
Qual è il valore del permanente di una data matrice le cui entrate sono 0 o 1? (Vedi Permanente è sharp-P-completo.)
Quante colorazioni dei grafi che usano k colori ci sono per un particolare grafo G?
Quante diverse estensioni lineari ci sono per un dato ordine parziale o, in modo equivalente, quanti diversi ordinamenti topologici ci sono per un dato grafo aciclico diretto?^[1]

Un algoritmo in tempo polinomiale per risolvere un problema #P-completo, se esistesse, implicherebbe P = NP, e così P = PH. Nessun algoritmo di questo tipo è attualmente noto.

Problemi facili con versioni di conteggio difficili modifica

È sorprendente che alcuni problemi #P-completi corrispondono a problemi P completi. È molto facile determinare la soddisfacibilità di una formula booleana in FND: tale formula è soddisfacibile se e solo se contiene una congiunzione soddisfacibile (una che non contiene una variabile e la sua negazione), mentre contare il numero di assegnazioni soddisfacenti è #P-completo. Anche decidere 2-SAT è facile al contrario del numero di assegnazioni soddisfacenti. Ordinare topologicamente è facile al contrario di contare il numero di ordinamenti topologici. La stessa osservazione si può fare per il problema dell'accoppiamento perfetto. Era noto prima che il problema decisionale "C'è un accoppiamento perfetto per un dato grafo bipartito?" può essere risolto in tempo polinomiale, e infatti, per un grafo con vertici V e spigoli E, può essere risolto nel tempo O(VE). La domanda corrispondente "Quanti accoppiamenti perfetti ha il grafo bipartito dato?" è già #P-completo. Il problema di contare il numero di accoppiamenti perfetti (o nei grafi diretti: si sa che il numero di coperture dei cicli dei vertici è equivalente al problema della computazione del permanente di una matrice. Il problema del conteggio degli accoppiamenti perfetti fu il primo problema di conteggio corrispondente a un problema P facile che si dimostrò essere #P-completo, in un saggio del 1979 di Leslie Valiant che definì anche le classi #P e #P-completo per la prima volta.^[2]

Approssimazione modifica

Ci sono algoritmi probabilistici che restituiscono buone approssimazioni ad alcuni problemi #P-completi con alta probabilità. Questa è una delle dimostrazioni della potenza degli algoritmi probabilistici.

Molti problemi #P-completi hanno uno schema di approssimazione randomizzato in tempo pienamente polinomiale, o "FPRAS," che, informalmente, produrrà con alta probabilità un'approssimazione a un grado arbitrario di accuratezza, in un tempo che è polinomiale sia rispetto alla dimensione del problema che al grado di accuratezza richiesto. Jerrum, Valiant e Vazirani mostrarono che ogni problema #P-completo o ha un FPRAS, o è essenzialmente impossibile da approssimare; se c'è un qualsiasi algoritmo in tempo polinomiale che produce coerentemente un'approssimazione di un problema #P-completo che è entro un rapporto che ha la dimensione dell'input della risposta esatta, allora quell'algoritmo può essere usato per costruire un FPRAS.^[3]

Note modifica

^ Graham R. Brightwell e Peter Winkler, Counting linear extensions, in Order, vol. 8, n. 3, 1991, 225–242, DOI:10.1007/BF00383444.
^ Leslie G. Valiant, The Complexity of Computing the Permanent, in Theoretical Computer Science, vol. 8, n. 2, Elsevier, 1979, 189–201, DOI:10.1016/0304-3975(79)90044-6.
^ Mark R. Jerrum, Leslie G. Valiant; Vijay V. Vazirani, Random Generation of Combinatorial Structures from a Uniform Distribution, in Theoretical Computer Science, vol. 32, Elsevier, 1986, 169–188.