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

Geometria computazionale

• Triangolazione di peso minimo per un insieme di punti del piano
• 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)
• 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.

Teoria dei grafi

Copertura e partizionamento

• 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

• 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

• 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

• Digraph D-morphism
• Graph contractability
• Graph homomorphism
• Isomorfismo di sottografi
• Largest common subgraph
• Maximum subgraph matching

Vari

• Graph Grundy numbering
• Intersection graph basis
• K-closure
• Kernel
• Metric dimension
• Multiple choice matching
• Nesetril-Rödl dimension
• Oriented diameter
• Path distinguishers
• Path with forbidden pairs
• Threshold number
• Weighted diameter

Progettazione di reti

Alberi di copertura

• 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

• 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)

• 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

• 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

• 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

Copertura, hitting e divisione

• 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

• 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

• Median partition

Memorizzazione e ricerca

Memorizzazione di dati

• 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

• 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

• 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

Sequencing on one processor

• 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

• Multiprocessor scheduling
• Precedence constrained scheduling
• Resource constrained scheduling
• Scheduling with individual deadlines
• Preemptive scheduling
• Scheduling to minimize weighted completion time

Shop scheduling

• Open-shop scheduling
• Flow-shop scheduling
• No-wait flow-shop scheduling
• Two-processor flow-shop with bounded buffer
• Job-shop scheduling

Miscellanea

• Timetable design
• Staff scheduling
• Production planning
• Deadlock avoidance

Programmazione matematica

• 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

Problemi di divisibilità

• 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

• 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[2ⁿ], n the length of the input.

Miscellanea

• Permanent evaluation
• Cosine product integration
• Equilibrium point
• Unification with commutative operators
• Unification for finitely presented algebras
• Integer expression membership
• Minimal addition chain

Giochi e puzzle

• 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

Logica proposizionale

• 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

• 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

Teoria degli automi

• 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

Linguaggi formali

• 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

Generazione di codice

• 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

• 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

• 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

• Karp's 21 NP-complete problems
• List of PSPACE-complete problems

Note

• 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.