Sharp-P

Nella teoria della complessità computazionale, la classe di complessità #P (pronunciata "sharp P" o, a volte, "numero P" o "cancelletto P") è l'insieme dei problemi di conteggio associati ai problemi decisionali nell'insieme NP. Più formalmente, #P è la classe dei problemi di funzione della forma "computa ƒ(x)", dove ƒ è il numero di percorsi di accettazione di una macchina di Turing non deterministica che funziona in tempo polinomiale. Diversamente dalle maggior parte delle classi di complessità note, non è una classe di problemi di decisione, ma una classe di problemi di funzione.

Un problema NP ha spesso la forma "Ci sono soluzioni che soddisfano certi vincoli?" Per esempio:

Ci sono sottoinsiemi di una lista di interi che danno come somma zero? (problema della somma di sottoinsiemi)
Ci sono cicli hamiltoniani in un dato grafo con un costo minore di 100? (problema del commesso viaggiatore)
Ci sono assegnazioni variabili che soddisfano una data formula FNC? (problema di soddisfacibilità booleana)

I problemi #P corrispondenti chiedono "quanti" piuttosto che "ci sono". Ad esempio:

Quanti sottoinsiemi di una lista di interi danno come somma zero?
Quanti cicli hamiltoniani in un dato grafo hanno un costo minore di 10?
Quante assegnazioni variabili soddisfano una data formula FNC?

Chiaramente, un problema #P deve essere difficile almeno quanto il corrispondente problema NP. Se è facile contare le risposte, allora deve essere facile dire se ci sono risposte – basta contarle e vedere se il conto è maggiore di zero.

Una conseguenza del teorema di Toda è che una macchina in tempo polinomiale con un oracolo #P (P^#P) può risolvere tutti i problemi in PH, l'intera gerarchia polinomiale. Infatti, la macchina in tempo polinomiale ha bisogno di fare solo una interrogazione in #P per risolvere qualsiasi problema in PH. Questa è un'indicazione dell'estrema difficoltà di risolvere esattamente i problemi #P-completi.

Sorprendentemente, alcuni problemi #P che si credono difficili corrispondono a problemi P facili. Per maggiori informazioni su questo argomento, vedi #P-completo.

La classe di problemi decisionali più vicina a #P è PP, che domanda se una maggioranza (più della metà) dei percorsi di computazione accettano la risposta. Essa trova il bit più significativo nella risposta del problema #P. La classe dei problemi decisionali ⊕P chiede invece il bit meno significativo della risposta di #P.

La classe di complessità #P fu definita per la prima volta da Leslie Valiant in un articolo del 1979 sulla computazione del permanente, in cui dimostrò che il permanente è #P-completo.^[1]

Larry Stockmeyer ha provato che per ogni problema P di #P esiste un algoritmo randomizzato che usa un oracolo per SAT, che data un'istanza a di P and ε > 0 restituisce con alta probabilità un numero x tale che $(1-\epsilon )P(a)\leq x\leq (1+\epsilon )P(a)$ . Il tempo di esecuzione dell'algoritmo è polinomiale in a e 1/ε. L'algoritmo si basa sul lemma leftover hash.