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? * 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 è che una macchina in tempo polinomiale con un #P (P#P) può risolvere tutti i problemi in , l'intera . 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 è , 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 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. 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 . Il tempo di esecuzione dell'algoritmo è polinomiale in a e 1/ε. L'algoritmo si basa sul lemma leftover hash.