Sharp-P

Nella teoria della complessità computazionale, la classe di complessità ♯P (pronunciata in inglese "sharp 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.

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.

Collegamenti esterni

• (EN) Classe #P, su Complexity Zoo (archiviato dall'url originale il 19 gennaio 2018).