René's URL Explorer Experiment


Title: NP-Complete Problem -- from Wolfram MathWorld

Open Graph Title: NP-Complete Problem -- from Wolfram MathWorld

X Title: NP-Complete Problem -- from Wolfram MathWorld

Description: A problem which is both NP (verifiable in nondeterministic polynomial time) and NP-hard (any NP-problem can be translated into this problem). Examples of NP-hard problems include the Hamiltonian cycle and traveling salesman problems. In a landmark paper, Karp (1972) showed that 21 intractable combinatorial computational problems are all NP-complete.

Open Graph Description: A problem which is both NP (verifiable in nondeterministic polynomial time) and NP-hard (any NP-problem can be translated into this problem). Examples of NP-hard problems include the Hamiltonian cycle and traveling salesman problems. In a landmark paper, Karp (1972) showed that 21 intractable combinatorial computational problems are all NP-complete.

X Description: A problem which is both NP (verifiable in nondeterministic polynomial time) and NP-hard (any NP-problem can be translated into this problem). Examples of NP-hard problems include the Hamiltonian cycle and traveling salesman problems. In a landmark paper, Karp (1972) showed that 21 intractable combinatorial computational problems are all NP-complete.

Opengraph URL: https://mathworld.wolfram.com/NP-CompleteProblem.html

X: @WolframResearch

direct link

Domain: mathworld.wolfram.com

DC.TitleNP-Complete Problem
DC.CreatorWeisstein, Eric W.
DC.DescriptionA problem which is both NP (verifiable in nondeterministic polynomial time) and NP-hard (any NP-problem can be translated into this problem). Examples of NP-hard problems include the Hamiltonian cycle and traveling salesman problems. In a landmark paper, Karp (1972) showed that 21 intractable combinatorial computational problems are all NP-complete.
DC.Subject68W40
DC.RightsCopyright 1999-2026 Wolfram Research, Inc. See https://mathworld.wolfram.com/about/terms.html for a full terms of use statement.
DC.Formattext/html
DC.Identifierhttps://mathworld.wolfram.com/NP-CompleteProblem.html
DC.Languageen
DC.PublisherWolfram Research, Inc.
DC.Relation.IsPartOfhttps://mathworld.wolfram.com/
DC.TypeText
og:imagehttps://mathworld.wolfram.com/images/socialmedia/share.png
og:typewebsite
twitter:cardsummary_large_image
twitter:image:srchttps://mathworld.wolfram.com/images/socialmedia/share.png
Noneie=edge

Links:

https://www.wolfram.com/mathematica/
https://wolframalpha.com/
https://mathworld.wolfram.com/
https://www.wolfram.com/mathematica/
https://wolframalpha.com/
https://mathworld.wolfram.com/
Algebra https://mathworld.wolfram.com/topics/Algebra.html
Applied Mathematics https://mathworld.wolfram.com/topics/AppliedMathematics.html
Calculus and Analysis https://mathworld.wolfram.com/topics/CalculusandAnalysis.html
Discrete Mathematics https://mathworld.wolfram.com/topics/DiscreteMathematics.html
Foundations of Mathematics https://mathworld.wolfram.com/topics/FoundationsofMathematics.html
Geometry https://mathworld.wolfram.com/topics/Geometry.html
History and Terminology https://mathworld.wolfram.com/topics/HistoryandTerminology.html
Number Theory https://mathworld.wolfram.com/topics/NumberTheory.html
Probability and Statistics https://mathworld.wolfram.com/topics/ProbabilityandStatistics.html
Recreational Mathematics https://mathworld.wolfram.com/topics/RecreationalMathematics.html
Topology https://mathworld.wolfram.com/topics/Topology.html
Alphabetical Index https://mathworld.wolfram.com/letters/
New in MathWorld https://mathworld.wolfram.com/whatsnew/
Discrete Mathematicshttps://mathworld.wolfram.com/topics/DiscreteMathematics.html
Computer Sciencehttps://mathworld.wolfram.com/topics/ComputerScience.html
Algorithmshttps://mathworld.wolfram.com/topics/Algorithms.html
Complexity of Algorithmshttps://mathworld.wolfram.com/topics/ComplexityofAlgorithms.html
NPhttps://mathworld.wolfram.com/NP-Problem.html
polynomial timehttps://mathworld.wolfram.com/PolynomialTime.html
NP-hardhttps://mathworld.wolfram.com/NP-HardProblem.html
NP-problemhttps://mathworld.wolfram.com/NP-Problem.html
Hamiltonian cyclehttps://mathworld.wolfram.com/HamiltonianCycle.html
traveling salesman problemshttps://mathworld.wolfram.com/TravelingSalesmanProblem.html
Graph Isomorphism Completehttps://mathworld.wolfram.com/GraphIsomorphismComplete.html
Hamiltonian Cyclehttps://mathworld.wolfram.com/HamiltonianCycle.html
NP-Hard Problemhttps://mathworld.wolfram.com/NP-HardProblem.html
NP-Problemhttps://mathworld.wolfram.com/NP-Problem.html
P-Problemhttps://mathworld.wolfram.com/P-Problem.html
P Versus NP Problemhttps://mathworld.wolfram.com/PVersusNPProblem.html
Traveling Salesman Problemhttps://mathworld.wolfram.com/TravelingSalesmanProblem.html
np-complete problem https://www.wolframalpha.com/input/?i=np-complete+problem
NP-complete problems https://www.wolframalpha.com/input/?i=NP-complete+problems
Bode plot of s/(1-s) sampling period .02https://www.wolframalpha.com/input/?i=Bode+plot+of+s%2F%281-s%29+sampling+period+.02
Distance in Graphs.http://www.amazon.com/exec/obidos/ASIN/0201095912/ref=nosim/ericstreasuretro
Computers and Intractability: A Guide to the Theory of NP-Completeness.http://www.amazon.com/exec/obidos/ASIN/0716710447/ref=nosim/ericstreasuretro
Complexity of Computer Computations, Proc. Sympos. IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., 1972http://www.amazon.com/exec/obidos/ASIN/0306307073/ref=nosim/ericstreasuretro
Combinatorial Optimization: Algorithms and Complexity.http://www.amazon.com/exec/obidos/ASIN/0486402584/ref=nosim/ericstreasuretro
NP-Complete Problemhttps://www.wolframalpha.com/input/?i=np-complete+problem
Weisstein, Eric W.https://mathworld.wolfram.com/about/author.html
MathWorldhttps://mathworld.wolfram.com/
https://mathworld.wolfram.com/NP-CompleteProblem.htmlhttps://mathworld.wolfram.com/NP-CompleteProblem.html
Discrete Mathematicshttps://mathworld.wolfram.com/topics/DiscreteMathematics.html
Computer Sciencehttps://mathworld.wolfram.com/topics/ComputerScience.html
Algorithmshttps://mathworld.wolfram.com/topics/Algorithms.html
Complexity of Algorithmshttps://mathworld.wolfram.com/topics/ComplexityofAlgorithms.html
About MathWorldhttps://mathworld.wolfram.com/about/
MathWorld Classroomhttps://mathworld.wolfram.com/classroom/
Contributehttps://mathworld.wolfram.com/contact/
MathWorld Bookhttps://www.amazon.com/exec/obidos/ASIN/1420072218/ref=nosim/weisstein-20
wolfram.comhttps://www.wolfram.com
13,439 Entrieshttps://mathworld.wolfram.com/whatsnew/
Last Updated: Mon Jul 6 2026https://mathworld.wolfram.com/whatsnew/
©1999–2026 Wolfram Research, Inc.https://www.wolfram.com
Terms of Usehttps://www.wolfram.com/legal/terms/mathworld.html
https://www.wolfram.com
wolfram.comhttps://www.wolfram.com
Wolfram for Educationhttps://www.wolfram.com/education/

Viewport: width=device-width, initial-scale=1

URLs of crawlers that visited me.