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]

Teoria dei grafi[modifica]

Copertura e partizionamento[modifica]

Sottografi e sopragrafi[modifica]

Ordinamento di vertici[modifica]

Iso- ed altri morfismi[modifica]

Vari[modifica]

Progettazione di reti[modifica]

Alberi di copertura[modifica]

Tagli e connessione[modifica]

Problemi di instradamento (routing)[modifica]

Problemi di flusso[modifica]

Vari[modifica]

Insiemi e partizioni[modifica]

Copertura, hitting e divisione[modifica]

Problemi con insiemi pesati[modifica]

Partizione di insieme[modifica]

Memorizzazione e ricerca[modifica]

Memorizzazione di dati[modifica]

Compressione e rappresentazione[modifica]

Problemi di basi di dati[modifica]

Sequenza e programmazione[modifica]

Sequencing on one processor[modifica]

Programmazione multiprocessore[modifica]

Shop scheduling[modifica]

Miscellanea[modifica]

Programmazione matematica[modifica]

Algebra e teoria dei numeri[modifica]

Problemi di divisibilità[modifica]

Solvibilità di equazioni[modifica]

Miscellanea[modifica]

Giochi e puzzle[modifica]

Logica[modifica]

Logica proposizionale[modifica]

Miscellanea[modifica]

Automi and teoria del linguaggio[modifica]

Teoria degli automi[modifica]

Linguaggi formali[modifica]

Ottimizzazione di programmi[modifica]

Generazione di codice[modifica]

Programmi e schemi[modifica]

Miscellanea[modifica]

Voci correlate[modifica]

Note[modifica]

  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