Progetto:Informatica/Voci richieste/Problemi NP-Completi
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
- Triangolazione di peso minimo per un insieme di punti del piano [1]
- Verificare se un albero può essere rappresentato come albero di copertura euclideo
- Riconoscimento degli Unit disk graph (Gli Unit disk graphs sono grafi d'intersezione di cerchi di raggio unitario nel piano)[2]
- Molti motion planning tra ostacoli poligonali nel piano.
- Planar partitioning into connected subassemblies: Dato un insieme A di poligoni nel piano non sovrapposti (ma che potrebbero toccarsi), decidere se esiste un sottoinsieme proprio S di A che può essere separato da A\S mediante movimenti rigidi privi di collisioni di S e tale che sia S che A\S sono connessi. [3]
Teoria dei grafi
modificaCopertura e partizionamento
modifica- Numero acromatico
- Problema dell'allocazione di Berth(BAP)
- Rivestimento con sottografi completi bipartiti
- Colorazione di grafi
- Problema della cricca
- Numero di Domatic
- Feedback arc set
- Feedback vertex set
- Numero di Grundy
- Insieme dominante
- Accoppiamento (teoria dei grafi)
- Monochromatic triangle
- Partial feedback edge set
- Partition into Hamiltonian subgraphs
- Partition into cliques
- Partition into forests
- Partition into isomorphic subgraphs
- Partition into perfect matchings
- Partition into triangles
- Problema di copertura dei vertici
- Two-stage maximum weight stochastic matching
Sottografi e sopragrafi
modifica- Balanced complete bipartite subgraph
- Bipartite subgraph
- Clique
- Cubic subgraph
- Degree-bounded connected subgraph
- Edge-subgraph
- Hamiltonian completion
- Independent set
- Induced connected subgraph with property Pi
- Induced path
- Induced subgraph with property Pi
- Interval graph completion
- Minimum equivalent digraph
- Minimum k-connected subgraph
- Path graph completion]
- Planar subgraph
- Transitive subgraph
- Uniconnected subgraph
Ordinamento di vertici
modifica- Bandwidth
- Directed Hamiltonian circuit
- Directed bandwidth
- Directed elimination ordering
- Directed optimal linear arrangement
- Elimination degree sequence]
- Hamiltonian circuit
- Hamiltonian path
- Minimum cut linear arrangement
- Optimal linear arrangement
- Rooted tree arrangement
Iso- ed altri morfismi
modifica- Digraph D-morphism
- Graph contractability
- Graph homomorphism
- Isomorfismo di sottografi
- Largest common subgraph
- Maximum subgraph matching
Vari
modificaProgettazione di reti
modificaAlberi di copertura
modifica- Degree-constrained spanning tree
- Minimum degree spanning tree
- Maximum leaf spanning tree
- Shortest total path length spanning tree
- Bounded diameter spanning tree
- Capacitated spanning tree
- Geometric capacitated spanning tree
- Optimum communication spanning tree
- Isomorphic spanning tree
- Kth best spanning tree
- Bounded component spanning forest
- Multiple choice branching
- Steiner tree
- Geometric Steiner tree
- Cable Trench Problem
- Minimum Touching Tree/Minimum Length Corridor
Tagli e connessione
modifica- Graph partitioning
- Acyclic partition
- Max weight cut
- Minimum cut into bounded sets
- Biconnectivity augmentation
- Strong connectivity augmentation
- Network reliability
- Network survivability
- Multiway Cut
- Minimum k-cut
- k-vital edges
Problemi di instradamento (routing)
modifica- Bottleneck traveling salesman
- Chinese postman for mixed graphs
- Commesso viaggiatore
- Euclidean traveling salesman
- K most vital arcs
- Kth shortest path
- Metric traveling salesman
- Longest circuit
- Longest path
- Prize Collecting Traveling Salesman
- Rural Postman
- Shortest path in general networks
- Shortest weight-constrained path
- Stacker-crane
- Time constrained traveling salesman feasibility
- Vehicle routing problem
Problemi di flusso
modifica- Minimum edge-cost flow
- Integral flow with multipliers
- Path constrained network flow
- Integral flow with homologous arcs
- Integral flow with bundles
- Undirected flow with lower bounds
- Directed two-commodity integral flow
- Undirected two-commodity integral flow
- Disjoint connecting paths
- Maximum length-bounded disjoint paths
- Maximum fixed-length disjoint paths
- Unsplittable multicommodity flow
Vari
modifica- Quadratic assignment problem
- Minimizing dummy activities in PERT networks
- Constrained triangulation
- Intersection graph for segments on a grid
- Edge embedding on a grid
- Geometric connected dominating set
- Minimum broadcast time
- Min-max multicenter
- Min-sum multicenter
- Uncapacitated Facility Location
- Metric k-center
Insiemi e partizioni
modificaCopertura, hitting e divisione
modifica- 3-dimensional matching
- Exact cover
- Set packing
- Set splitting
- Set cover
- Minimum test set
- Set basis
- Hitting set
- Intersection pattern
- Comparative containment
- 3-matroid intersection
Problemi con insiemi pesati
modifica- Partition
- Subset sum
- Subset product
- 3-partition
- Numerical 3-dimensional matching
- Numerical matching with target sums
- Expected component sum
- Minimum sum of squares
- Kth largest subset
- Kth largest m-tuple
Partizione di insieme
modificaMemorizzazione e ricerca
modificaMemorizzazione di dati
modifica- Bin packing
- Dynamic storage allocation
- Pruned trie space minimization
- Expected retrieval cost
- Rooted tree storage assignment
- Multiple copy file allocation
- Capacity assignment
Compressione e rappresentazione
modifica- Shortest common supersequence
- Shortest common superstring
- Longest common subsequence problem for the case of arbitrary (i.e., not a priori fixed) number of input sequences even in the case of the binary alphabet
- Bounded post correspondence problem
- Hitting string
- Sparse matrix compression
- Consecutive ones submatrix
- Consecutive ones matrix partition
- Consecutive ones matrix augmentation
- Consecutive block minimization
- Consecutive sets
- 2-dimensional consecutive sets
- String-to-string correction
- Grouping by swapping
- External macro data compression
- Internal macro data compression
- Regular expression substitution
- Rectilinear picture compression
- Optimal vector quantization codebook
- Minimal grammar-based compression
- Adaptive Block-size Compression
Problemi di basi di dati
modifica- Minimum cardinality key
- Additional key
- Prime attribute name
- Boyce-Codd normal form violation
- Conjunctive query foldability
- Boolean conjunctive query
- Tableau equivalence
- Serializability of database histories
- Safety of database transaction systems
- Consistency of database frequency tables
- Safety of file protection systems
Sequenza e programmazione
modificaSequencing on one processor
modifica- Sequencing with release times and deadlines
- Sequencing to minimize Tardy tasks
- Sequencing to minimize Tardy weight
- Sequencing to minimize weighted completion time
- Sequencing to minimize weighted tardiness
- Sequencing with deadlines and set-up times
- Sequencing to minimize maximum cumulative cost
Programmazione multiprocessore
modifica- Multiprocessor scheduling
- Precedence constrained scheduling
- Resource constrained scheduling
- Scheduling with individual deadlines
- Preemptive scheduling
- Scheduling to minimize weighted completion time
Shop scheduling
modifica- Open-shop scheduling
- Flow-shop scheduling
- No-wait flow-shop scheduling
- Two-processor flow-shop with bounded buffer
- Job-shop scheduling
Miscellanea
modificaProgrammazione matematica
modifica- Comparative vector inequalities
- Continuous multiple choice knapsack
- Cost-parametric linear programming
- Feasible basis extension
- Generalized assignment problem
- Integer knapsack
- Programmazione intera
- K-relevancy
- programmazione intera 0-1
- Minimum weight solution to linear equations
- Open hemisphere
- Partially ordered knapsack
- Problema dello zaino
- Quadratic programming (NP-hard in certi casi, P se convessa)
- Sparse approximation
- Traveling salesman polytope non-adjacency
Algebra e teoria dei numeri
modificaProblemi di divisibilità
modifica- Quadratic congruences
- Simultaneous incongruences
- Simultaneous divisibility of linear polynomials
- Comparative divisibility
- Exponential expression divisibility
- Non-divisibility of a product polynomial
- Non-trivial greatest common divisor
Solvibilità di equazioni
modifica- Quadratic diophantine equations
- Algebraic equations over GF[2]
- Root of modulus 1
- Number of roots for a product polynomial
- Periodic solution recurrence relation
- Non-linear univariate polynomials over GF[2n], n the length of the input.
Miscellanea
modificaGiochi e puzzle
modifica- Alternating hitting set
- Alternating maximum weighted matching
- Annihilation
- Battleship
- Clickomania (SameGame)
- Kakuro (somme incrociate)
- Costruzione di schemi di parole crociate
- Freecell
- Instant Insanity
- Light Up
- LITS
- Mastermind
- Masyu
- Campo minato (videogioco)
- Nurikabe
- Paint by numbers (Nonogram)
- Rabin game
- Sift
- Slither Link
- Square-tiling
- Sudoku
- Tetris
- Variable partition truth assignment
- Verbal arithmetic
Logica
modificaLogica proposizionale
modifica- Soddisfacibilità booleana
- 3-Satisfiability
- Not-all-equal 3SAT
- One-in-three 3SAT
- Maximum 3-Satisfiability
- Generalized satisfiability
- Non-tautology
- Minimum disjunctive normal form
- Truth-functionally complete connectives
- Planar-3SAT
- Monotone-3SAT
Miscellanea
modifica- Modal logic S5-Satisfiability
- Negation-free logic
- Conjunctive satisfiability with functions and inequalities
- Minimum axiom set
- First order subsumption
- Second order instantiation
Automi and teoria del linguaggio
modificaTeoria degli automi
modifica- Non nullità negli automi a stati finiti a due vie
- Quasi-realtime automaton acceptance
- Riduzione di un automa non completamente specificato
- Minimum inferred finite state automaton
- Minimum inferred regular expression
- Reynolds covering for context-free grammars
- Covering for linear grammars
- Structural inequivalence for linear grammars
- Regular grammar inequivalence
- Non-LR(K) context-free grammar
- Etol grammar non-emptiness
- Context-free programmed language membership
- Quasi-real-time language membership
- Etol language membership
- Tree transducer language membership
Ottimizzazione di programmi
modificaGenerazione di codice
modifica- Register sufficiency
- Feasible register assignment
- Register sufficiency for loops
- Code generation on a one-register machine
- Code generation with unlimited registers
- Code generation for parallel assignments
- Code generation with address expressions
- Code generation with unfixed variable locations
- Ensemble computation
- Microcode bit optimization
Programmi e schemi
modifica- Inequivalence of programs with arrays
- Inequivalence of programs with assignments
- Inequivalence of finite memory programs
- Inequivalence of loop programs without nesting
- Inequivalence of simple functions
- Strong inequivalence of Ianov schemes
- Strong inequivalence for monadic recursion
- Non-containment for free B-schemes
- Non-freedom for loop-free program schemes
- Programs with formally recursive procedures
Miscellanea
modifica- Cyclic ordering
- Non-liveness of free choice Petri nets
- Reachability for 1-conservative Petri nets
- Finite function generation
- Permutation generation
- Decoding of linear codes
- Shapley-Shubik voting power
- Clustering
- Randomization test for matched pairs
- Maximum likelihood ranking
- Matrix domination
- Matrix cover
- Simply deviated disjunction
- Decision tree
- Minimum weight and/or graph solution
- Fault detection in logic circuits
- Fault detection in directed graphs
- Fault detection with test points
Voci correlate
modificaNote
modifica- ^ Minimum Weight Triangulation is NP-Hard, 22nd SCG (2006)
- ^ H. Breu and David G. Kirkpatrick. "Unit Disk Graph Recognition is NP-hard." Comput. Geom. Theory Appl., 9(1-2):3--24, 1998
- ^ "Assembly Into Two Connected Parts Is NP-Complete", Inf. Proc. Letters 55 (1995), 159-165.
- M.R. Garey, Johnson, D.S., Computers and Intractability: A Guide to the Theory of NP-Completeness, New York, W.H. Freeman, 1979, ISBN 0-7167-1045-5.
- S.A. Cook, The complexity of theorem proving procedures, in Proceedings, Third Annual ACM Symposium on the Theory of Computing, ACM, New York, 1971, pp. 151–158, DOI:10.1145/800157.805047.
- P.E Dunne, An annotated list of selected NP-complete problems, su csc.liv.ac.uk, COMP202, Dept. of Computer Science, University of Liverpool. URL consultato il 21 giugno 2008.
- P. Crescenzi, Kann, V.; Halldórsson, M.; Karpinski, M.; Woeginger, G, A compendium of NP optimization problems, su nada.kth.se, KTH NADA, Stockholm. URL consultato il 21 giugno 2008.
- K Dahlke, NP-complete problems, su Math Reference Project. URL consultato il 21 giugno 2008.
- E Friedman, Pearl puzzles are NP-complete, su stetson.edu, Stetson University, DeLand, Florida, 2002. URL consultato il 21 giugno 2008.
