Sharp-P

Da Wikipedia, l'enciclopedia libera.

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 speso la forma "Ci sono soluzioni che soddisfano certi vincoli?" Per esempio:

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.

Note[modifica | modifica wikitesto]

  1. ^ Leslie G. Valiant, The Complexity of Computing the Permanent in Theoretical Computer Science, vol. 8, nº 2, Elsevier, 1979, pp. 189–201, DOI:10.1016/0304-3975(79)90044-6.

Collegamenti esterni[modifica | modifica wikitesto]