Metraipolis › archive › dc_44f75da4378b

Sharp-P-completo — Wikipedia

Source
Wikipedia (it)
Original
https://it.wikipedia.org/wiki/Sharp-P-completo
License (as archived)
CC-BY-SA-4.0
Archived
2026-11-09T10:11:24.314Z
SHA-256 of the archived text
ebc2deaf3d06c6df1020f89f075eb8753e77320418f0443e26856080b7e8a034
Stable URL of this page
https://metraipolis.com/documento/dc_44f75da4378b

How to cite

Sharp-P-completo — Wikipedia — Wikipedia (it), https://it.wikipedia.org/wiki/Sharp-P-completo (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_44f75da4378b (Metraipolis archive dc_44f75da4378b, sha256 ebc2deaf3d06c6df1020f89f075eb8753e77320418f0443e26856080b7e8a034)
BibTeX
@misc{dc44f75da4378b,
  title = {Sharp-P-completo — Wikipedia},
  howpublished = {Wikipedia (it)},
  url = {https://it.wikipedia.org/wiki/Sharp-P-completo},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_44f75da4378b; sha256 ebc2deaf3d06c6df1020f89f075eb8753e77320418f0443e26856080b7e8a034},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (it), https://it.wikipedia.org/wiki/Sharp-P-completo. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Nella teoria della complessità computazionale, un problema computazionale è detto ♯P-completo (pronunciato "sharp P completo") se e solo se è in #P e ogni problema in #P può essere ridotto ad esso da una riduzione per conteggio 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? (#SAT) 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 Permanente è sharp-P-completo.) Quante colorazioni dei grafi che usano k colori ci sono per un particolare grafo G? Quante diverse estensioni lineari 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 = PH. Nessun algoritmo di questo tipo è attualmente noto.

Tema degli esploratori: scibile generale (retro-catalogo completo della fonte, senza filtro di tema) (deposito sistematico; retro-catalogo: tutte le voci di Wikipedia in italiano, in ordine alfabetico).
Fonte: Wikipedia in italiano, voce «Sharp-P-completo» — https://it.wikipedia.org/wiki/Sharp-P-completo
Wikidata Q841545: «classe di complessità» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q841545
Autori: i contributori di Wikipedia (cronologia: https://it.wikipedia.org/wiki/Sharp-P-completo?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 151122310, consultata il 2026-11-09T10:05:50.265Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 84d203975b66b6c1c15dc2cb3acb6caedc8fe183db7576e612f660bb9b5fa316