NP-completeness

Angol

Főnév

NP-completeness (tsz. NP-completenesses)

(informatika) NP-teljesség

NP-complete (magyarul: NP-teljes) problémák azok a döntési problémák, amelyek:

Az NP osztályba tartoznak: azaz polinomiális időben ellenőrizhető a megoldásuk,
NP-nehézek: azaz minden más NP-probléma polinomiális időben visszavezethető rájuk.

👉 Ez az osztály a „leghardcore-abb” nehézségi szintje annak, amit ellenőrizni könnyű, de megoldani nehéz.

🧠 1. Mi az NP?

Az NP (nondeterministic polynomial time) osztály azon problémák halmaza, amelyekre, ha valaki ad egy megoldást, azt gyorsan (polinomiális időben) ellenőrizni tudjuk.

📐 2. Definíció: NP-complete

Egy döntési probléma akkor NP-complete, ha:

${\textstyle L\in {\text{NP}}}$
Minden ${\textstyle L'\in {\text{NP}}}$ esetén: ${\textstyle L'\leq _{p}L}$ , azaz van polinomiális időbeli redukció ${\textstyle L'}$ -ből ${\textstyle L}$ -be

📦 3. Mit jelent ez gyakorlatban?

Ha bármelyik NP-teljes problémára találunk gyors (polinomiális idejű) algoritmust, akkor:

${\text{P}}={\text{NP}}$
Ez minden NP-probléma megoldhatóságát jelentené gyorsan.
Jelenleg nincs ismert algoritmus egyetlen NP-teljes probléma gyors megoldására, és nem bizonyított, hogy nincs.

🔁 4. Redukció – a kulcsművelet

Ha meg tudjuk mutatni, hogy:

Egy ismert NP-complete probléma polinomiális időben redukálható egy új problémára,
és az új probléma is az NP-ben van,

akkor az új probléma is NP-complete.

🔧 5. Első NP-teljes probléma: SAT

A Cook–Levin-tétel (1971) szerint:

A SAT (kielégíthetőségi probléma) NP-teljes.

Ez volt az első bizonyítottan NP-complete probléma, és az összes többi ehhez viszonyítva vált NP-teljessé.

🧮 6. Klasszikus NP-complete problémák

Probléma	Rövid leírás
3-SAT	Logikai formula 3 literálos klauzulákból
Clique	Van-e ${\textstyle k}$ -méretű klikk egy gráfban?
Vertex Cover	Lefedhető-e a gráf élei ${\textstyle k}$ csúccsal?
Hamiltonian cycle	Van-e zárt körút, ami minden csúcsot érint?
Subset sum	Van-e részhalmaz, amely adott összeget ad?
Knapsack (döntési változat)	Van-e olyan kiválasztás, amely nem lépi túl a súlyt és eléri az értéket?
Graph coloring	${\textstyle k}$ színnel színezhető-e a gráf szomszédos csúcsok nélkül?
TSP (döntési)	Van-e olyan körút, ami nem hosszabb ${\textstyle k}$ -nál?

📊 7. Vizualizáció – komplexitási hierarchia

          +-------------------+
          |   NP-complete     | ← nagyon nehéz
          +--------+----------+
                   |
                 ⬇ Redukció
+------------+    +-------------+    +----------+
|    P       | ⊆  |     NP      | ⊆ | PSPACE   |
+------------+    +-------------+    +----------+

🛠️ 8. Mi történne, ha P = NP?

Minden NP-complete probléma gyorsan megoldható lenne.
Titkosítás (pl. RSA, ECC) elvesztené biztonságát.
Számítási kreativitás (bizonyítás, optimalizálás, keresés) automatizálhatóvá válna.

De:

A legtöbb szakértő úgy véli, hogy P ≠ NP.

🧾 9. Összefoglalás

Fogalom	Leírás
NP-complete	Az NP osztály „legnehezebb” problémái
Tulajdonság	NP-ben vannak, és minden NP-probléma redukálható rájuk
Kulcstechnika	Polinomiális időbeli redukció
Fontos példák	SAT, Clique, TSP, Knapsack, Graph Coloring
Tét	Ha bármelyik megoldható gyorsan, akkor P = NP

NP-complete problems include:

graphs and hypergraphs

graphs occur frequently in everyday applications. examples include biological or social networks, which contain hundreds, thousands and even billions of nodes in some cases (e.g. facebook or linkedin).

1-planarity Sablon:sfnp
3-dimensional matching
bandwidth problem
bipartite dimension
capacitated minimum spanning tree
route inspection problem (also called chinese postman problem) for mixed graphs (having both directed and undirected edges). the program is solvable in polynomial time if the graph has all undirected or all directed edges. variants include the rural postman problem.
clique cover problem
clique problem
complete coloring, a.k.a. achromatic number
cycle rank
degree-constrained spanning tree
domatic number
dominating set, a.k.a. domination number

np-complete special cases include the edge dominating set problem, i.e., the dominating set problem in line graphs. np-complete variants include the connected dominating set problem and the maximum leaf spanning tree problem.

feedback vertex set
feedback arc set
graph coloring
graph homomorphism problem
graph partition into subgraphs of specific types (triangles, isomorphic subgraphs, hamiltonian subgraphs, forests, perfect matchings) are known np-complete. partition into cliques is the same problem as coloring the complement of the given graph. a related problem is to find a partition that is optimal terms of the number of edges between parts.
grundy number of a directed graph.
hamiltonian completion
hamiltonian path problem, directed and undirected.
induced subgraph isomorphism problem
graph intersection number
longest path problem
maximum bipartite subgraph or (especially with weighted edges) maximum cut.
maximum common subgraph isomorphism problem
maximum independent set
maximum induced path
minimum maximal independent set a.k.a. minimum independent dominating set

np-complete special cases include the minimum maximal matching problem,

metric dimension of a graph
metric k-center
minimum degree spanning tree
minimum k-cut
minimum k-spanning tree
minor testing (checking whether an input graph $g$ contains an input graph $h$ as a minor); the same holds with topological minors
steiner tree, or minimum spanning tree for a subset of the vertices of a graph. (the minimum spanning tree for an entire graph is solvable in polynomial time.)
modularity maximization
monochromatic triangle
pathwidth, or, equivalently, interval thickness, and vertex separation number
rank coloring
k-chinese postman
shortest total path length spanning tree
slope number two testing
recognizing string graphs
subgraph isomorphism problem
treewidth
testing whether a tree may be represented as euclidean minimum spanning tree
vertex cover

mathematical programming

3-partition problem
bin packing problem
bottleneck traveling salesman
uncapacitated facility location problem
flow shop scheduling problem
generalized assignment problem
integer programming. the variant where variables are required to be 0 or 1, called zero-one linear programming, and several other variants are also np-complete
some problems related to job-shop scheduling
knapsack problem, quadratic knapsack problem, and several variants
some problems related to multiprocessor scheduling
numerical 3-dimensional matching
open-shop scheduling
partition problem
quadratic assignment problem
quadratic programming (np-hard in some cases, p if convex)
subset sum problem
variations on the traveling salesman problem. the problem for graphs is np-complete if the edge lengths are assumed integers. the problem for points on the plane is np-complete with the discretized euclidean metric and rectilinear metric. the problem is known to be np-hard with the (non-discretized) euclidean metric.

formal languages and string processing

closest string
longest common subsequence problem over multiple sequences
the bounded variant of the post correspondence problem
shortest common supersequence over multiple sequences
extension of the string-to-string correction problem

games and puzzles

bag (corral)
battleship
bulls and cows, marketed as master mind: certain optimisation problems but not the game itself.
edge-matching puzzles
fillomino
(generalized) freecell
goishi hiroi
hashiwokakero
heyawake
(generalized) instant insanity
kakuro (cross sums)
kingdomino
kuromasu (also known as kurodoko)
lasertank
lemmings (with a polynomial time limit)
light up
mahjong solitaire (with looking below tiles)
masyu
minesweeper consistency problem (but see scott, stege, & van rooij)
nonograms
numberlink
nurikabe
(generalized) pandemic
peg solitaire
n-queens completion
optimal solution for the ${1|}$ rubik's cube
samegame
shakashaka
slither link on a variety of grids
(generalized) sudoku
tatamibari
tentai show
problems related to tetris
verbal arithmetic

other

berth allocation problem
betweenness
assembling an optimal bitcoin block.
boolean satisfiability problem (sat).
circuit satisfiability problem
conjunctive boolean query
cyclic ordering
exact cover problem. remains np-complete for 3-sets. solvable in polynomial time for 2-sets (this is a matching).
finding the global minimum solution of a hartree-fock problem
upward planarity testing
hospitals-and-residents problem with couples
knot genus
latin square completion (the problem of determining if a partially filled square can be completed)
maximum 2-satisfiability
maximum volume submatrix – problem of selecting the best conditioned subset of a larger $m\times n$ matrix. this class of problem is associated with rank revealing qr factorizations and d optimal experimental design.
minimal addition chains for sequences. the complexity of minimal addition chains for individual numbers is unknown.
modal logic s5-satisfiability
pancake sorting distance problem for strings
solubility of two-variable quadratic polynomials over the integers. given positive integers $\textstyle a,b,c$ , decide existence of positive integers $x,y$ such that $ax^{2}+by-c=0$
by the same article existence of bounded modular square roots with arbitrarily composite modulus. given positive integers $\textstyle a,b,c\geq 0$ , decide existence of an integer $x\in$ such that $x^{2}\equiv a{\bmod {b}}$ . the problem remains np-complete even if a prime factorization of $b$ is provided.
serializability of database histories
set cover (also called "minimum cover" problem). this is equivalent, by transposing the incidence matrix, to the hitting set problem.
set packing
set splitting problem
scheduling to minimize weighted completion time
block sorting (sorting by block moves)
sparse approximation
variations of the steiner tree problem. specifically, with the discretized euclidean metric, rectilinear metric. the problem is known to be np-hard with the (non-discretized) euclidean metric.
three-dimensional ising model