Progetto:Informatica/Voci richieste/Problemi NP-Completi

Da Wikipedia, l'enciclopedia libera.


Ecco alcuni dei più noti problemi che sono NP-completi quando vengono espressi come problemi decisionali. Questa lista non è assolutamente completa (sono noti più di 3000 problemi NP-completi). La maggior parte dei problemi in questa lista è presa dal fondamentale libro di Michael R. Garey e David S. Johnson Computers and Intractability: A Guide to the Theory of NP-Completeness


Geometria computazionale[modifica wikitesto]

Teoria dei grafi[modifica wikitesto]

Copertura e partizionamento[modifica wikitesto]

Sottografi e sopragrafi[modifica wikitesto]

Ordinamento di vertici[modifica wikitesto]

Iso- ed altri morfismi[modifica wikitesto]

Vari[modifica wikitesto]

Progettazione di reti[modifica wikitesto]

Alberi di copertura[modifica wikitesto]

Tagli e connessione[modifica wikitesto]

Problemi di instradamento (routing)[modifica wikitesto]

Problemi di flusso[modifica wikitesto]

Vari[modifica wikitesto]

Insiemi e partizioni[modifica wikitesto]

Copertura, hitting e divisione[modifica wikitesto]

Problemi con insiemi pesati[modifica wikitesto]

Partizione di insieme[modifica wikitesto]

Memorizzazione e ricerca[modifica wikitesto]

Memorizzazione di dati[modifica wikitesto]

Compressione e rappresentazione[modifica wikitesto]

Problemi di basi di dati[modifica wikitesto]

Sequenza e programmazione[modifica wikitesto]

Sequencing on one processor[modifica wikitesto]

Programmazione multiprocessore[modifica wikitesto]

Shop scheduling[modifica wikitesto]

Miscellanea[modifica wikitesto]

Programmazione matematica[modifica wikitesto]

Algebra e teoria dei numeri[modifica wikitesto]

Problemi di divisibilità[modifica wikitesto]

Solvibilità di equazioni[modifica wikitesto]

Miscellanea[modifica wikitesto]

Giochi e puzzle[modifica wikitesto]

Logica[modifica wikitesto]

Logica proposizionale[modifica wikitesto]

Miscellanea[modifica wikitesto]

Automi and teoria del linguaggio[modifica wikitesto]

Teoria degli automi[modifica wikitesto]

Linguaggi formali[modifica wikitesto]

Ottimizzazione di programmi[modifica wikitesto]

Generazione di codice[modifica wikitesto]

Programmi e schemi[modifica wikitesto]

Miscellanea[modifica wikitesto]

Voci correlate[modifica wikitesto]

Note[modifica wikitesto]

  1. ^ Minimum Weight Triangulation is NP-Hard, 22nd SCG (2006)
  2. ^ H. Breu and David G. Kirkpatrick. "Unit Disk Graph Recognition is NP-hard." Comput. Geom. Theory Appl., 9(1-2):3--24, 1998
  3. ^ "Assembly Into Two Connected Parts Is NP-Complete", Inf. Proc. Letters 55 (1995), 159-165.


Matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica