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 ad esso da una 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? * 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 .) * Quante colorazioni dei grafi che usano k colori ci sono per un particolare grafo G? * Quante diverse ci sono per un dato ordine parziale o, in modo equivalente, quanti diversi ordinamenti topologici ci sono per un dato grafo aciclico diretto? Un algoritmo in tempo polinomiale per risolvere un problema #P-completo, se esistesse, implicherebbe P = NP, e così P = . Nessun algoritmo di questo tipo è attualmente noto.