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 | modifica sorgente]

Teoria dei grafi[modifica | modifica sorgente]

Copertura e partizionamento[modifica | modifica sorgente]

Sottografi e sopragrafi[modifica | modifica sorgente]

Ordinamento di vertici[modifica | modifica sorgente]

Iso- ed altri morfismi[modifica | modifica sorgente]

Vari[modifica | modifica sorgente]

Progettazione di reti[modifica | modifica sorgente]

Alberi di copertura[modifica | modifica sorgente]

Tagli e connessione[modifica | modifica sorgente]

Problemi di instradamento (routing)[modifica | modifica sorgente]

Problemi di flusso[modifica | modifica sorgente]

Vari[modifica | modifica sorgente]

Insiemi e partizioni[modifica | modifica sorgente]

Covering, hitting, and splitting[modifica | modifica sorgente]

Weighted set problems[modifica | modifica sorgente]

Set partitions[modifica | modifica sorgente]

Storage and retrieval[modifica | modifica sorgente]

Data storage[modifica | modifica sorgente]

Compression and representation[modifica | modifica sorgente]

Database problems[modifica | modifica sorgente]

Sequencing and scheduling[modifica | modifica sorgente]

Sequencing on one processor[modifica | modifica sorgente]

Multiprocessor scheduling[modifica | modifica sorgente]

Shop scheduling[modifica | modifica sorgente]

Miscellanea[modifica | modifica sorgente]

Mathematical programming[modifica | modifica sorgente]

Algebra and number theory[modifica | modifica sorgente]

Divisibility problems[modifica | modifica sorgente]

Solvability of equations[modifica | modifica sorgente]

Miscellanea[modifica | modifica sorgente]

Games and puzzles[modifica | modifica sorgente]

Alternating hitting set

Logic[modifica | modifica sorgente]

Logica proposizionale[modifica | modifica sorgente]

Miscellanea[modifica | modifica sorgente]

Automata and language theory[modifica | modifica sorgente]

Automata theory[modifica | modifica sorgente]

Formal languages[modifica | modifica sorgente]

Program optimization[modifica | modifica sorgente]

Code generation[modifica | modifica sorgente]

Programs and schemes[modifica | modifica sorgente]

Miscellanea[modifica | modifica sorgente]

Voci correlate[modifica | modifica sorgente]

Note[modifica | modifica sorgente]

  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