Talk:NP-completeness

Accuracy

I don't like the word "likely" in this context. Either something is in P or it isn't. We just don't know which one it is yet. What we do know is that if any NP-hard problem is in P then all NP problems are in P.

Lawrence D'Anna

There seem to be some contradictions in this page. First it says "the NP-complete problems are the hardest problems in NP" and later it says "It isn't really correct to say that NP-complete problems are the hardest problems in NP". I didn't update the page because I am not an expert in this, but would someone please consider fixing this confusing bit?

Thanks,

Rodrigo de Salvo Braz

"It isn't really correct to say that NP-complete problems are the hardest problems in NP. Assuming that P and NP are not equal, there are guaranteed to be an infinite number of problems that are in NP, but are neither NP-complete nor in P. Some of these problems may actually have higher complexity than some of the NP-complete problems."

I've heard of phase transitions in NP-complete problems. How does one know that, if P is not equal to NP, then there are problems that are in NP but neither in P nor in NP-complete?

Thanks

David Bernier

There is a detailed explanation on pages 154-155 of Garey and Johnson. It follows from a 1975 theorem of Ladner that if P is not equal to NP, then for every NP-complete problem, there is a subproblem that can be recognized in polynomial time that is neither NP-complete nor in P. Dominus 21:22 Mar 14, 2003 (UTC)

NP-complete are the hardest problems in NP by definition (A problem is NP-complete if it belongs to NP and it can be used to solve any NP problem through a polynomial time reduction). SAT was proven to be NP complete by Cook. Other problems were proven to be NP-complete by solving the SAT problem with them. Jan David Mol 12:10 Jun 2, 2003 (UTC)

Might it be a good idea to change 'problems' in the first line (or even throughout) to 'decision problems'? See the wikipedia page on NP-equivalent for my reason. Léon Planken 22:29 Jun 19, 2003 (UTC)

Hi, does this following thing imply subexponential time for NP-complete problem? i can't find the manuscript but i saw it cited somewhere. does anyone know/read the mansucript? W.D. Smith. Finding the optimum N-city traveling salesman tour in the Euclidean plane in subexponential time and polynomial space. Manuscript, 1988. 68.121.211.14 01:51, 21 Apr 2005 (UTC)

The planar TSP problem is not NP-complete, as far as I know. I don't believe there is any subexponential algorithm for an NP-complete problem (unless something like O(2^n/log n) counts). Deco 06:13, 21 Apr 2005 (UTC)

planar tsp is definitely NP complete from reduction from planar ham cycle 68.121.211.14 19:15, 21 Apr 2005 (UTC)

Oops, okay. You're right, it's safer this way anyway (who knows what people will find). Deco 05:42, 22 Apr 2005 (UTC)

Correct me if I'm wrong, but planar Hamiltonian cycle is the problem of finding a Hamiltonian cycle in a planar graph, i.e. a graph which has no crossing edges when drawn on the plane. Planar TSP is the problem of finding a minimum-cost TSP cycle for points on the plane, i.e. the associated graph is complete with edges between every pair of points, and the distances are the Euclidean distances between the points. I don't see any simple reduction from planar Hamiltonian cycle to planar TSP. 27 Apr 2005

---

Citing the article:

"In complexity theory, the NP-complete problems are the most difficult problems in NP, in the sense that they are the ones most likely not to be in P. The reason is that if you could find a way to solve an NP-complete problem quickly, then you could use that algorithm to solve all NP problems quickly."

I understand that the issue here is not how "quickly" an algorithm can solve a given problem, but instead that you can calculate the time that the algorithm would need to solve the problem.

Carlos Badiola

NPI

I cut this paragraph:

"It isn't really correct to say that NP-complete problems are the hardest problems in NP. Assuming that P and NP are not equal, there are guaranteed to be an infinite number of problems that are in NP, but are neither NP-complete nor in P. Some of these problems may actually have higher complexity than some of the NP-complete problems."

Although P ≠ NP implies that NPI = NP−NPC−P is nonempty, problems in NPI can be reduced to problems in NPC whereas problems in NPC cannot be reduced to problems in NPI. It seems reasonable to describe this state of affairs as "problems in NPC are harder than problems in NPI". So the paragraph is misleading.

Discussion of NPI probably belongs somewhere. Gdr 21:40, 2004 Jul 21 (UTC)

Imperfect solutions - Approximation

Approximation: An algorithm that quickly finds a suboptimal solution that is within a
certain (often known) range of  the optimal one. Not all NP-complete problems have
good approximation algorithms, and for some problems finding a good 
approximation algorithm is enough to solve the problem itself.

In the paragraph above, I don't understand the bolded phrase. Can someone explain? -- Sundar 07:26, Nov 25, 2004 (UTC)

I don't understand it either. I guess what is meant that approximating some problems good is NP-hard and so essentially not easier than solving them exactly. I'll just remove it, since the other approaches don't have their "caveats" listed either.

Suboptimality

Having got used to the notion of optimality with relation only to performance, it didn't occur to me that it can be used with correctness (in the Approximation algorithms paragraph). May be, this is because I'm not a native speaker of English. Can someone reword it making it clear that we are talking about correctness? -- Sundar 08:33, Feb 3, 2005 (UTC)

Is this problem NP-complete?

I found this problem and wondered if it was NP-complete: You have a bunch of tasks that take different amounts of time and some tasks can't be started until other tasks are finished. You have unlimited resourses, can do different tasks in parallel, and are trying to find the shortest time to complete all the tasks.

I'm going to assume good faith that you're not trying to get us to do your homework for you. What you describe is essentially a scheduling problem, also called job or task sequencing, and was one of Karp's 21 NP-complete problems. He showed it NP-complete by reduction from the knapsack problem. The graph you describe is called a task dependency graph. Technically, the precise problem you describe is actually NP-hard (it's not NP-complete because it's not even a decision problem). Deco 05:24, 19 Jun 2005 (UTC)

Thanks!--SurrealWarrior 18:43, 20 Jun 2005 (UTC)

Ambiguous wording

The wording in the first part of the page confused me. According to computational problem, a “solution” to a problem is an algorithm, which takes inputs and gives valid outputs. But this page says that NP-complete problems are ones to which “solutions can be verified quickly.” From what I know, checking whether a solution is correct for all inputs is not what complexity classes are about. And, editing it to say “outputs can be verified quickly” also wouldn’t work, because it says that outputs have to be yes or no. I’ll use sudoku as an example: the “solution” is an algorithm which takes a sudoku puzzle, and outputs “yes” if it’s possible to solve, “no” otherwise. I don’t think it’s possible to verify that quickly, otherwise we could solve any sudoku quickly by verifying “yes” then verifying “no.” The thing that CAN be verified quickly is if the solution outputted some proof of “yes,” like an actually filled-in grid. The same thing applies to other problems. If the problem is “for a graph of cities, can a salesman hit all of them while traveling less than 100km total?” you can’t verify a “solution” (algorithm) or “output” (yes/no), you can verify an actual path between the cities. I’m not sure how to edit this to make it make sense, but I think the first 3 bullet points need to be edited. Thank you in advance. SacrifycedStoat (talk) 06:51, 21 August 2026 (UTC)

The lead of this article clearly states what it means by a solution. It happens to be different from the meaning at computational problem. For your example of sudoku, the solution is neither an algorithm nor the yes-no output of a decision algorithm: it is the filled-in grid. I'm not sure there's much to be done about somewhat-related articles using colloquial words like "solution" to mean different concepts.

In technical writing on NP-completeness, what is here called a solution (such as a filled-in sudoku grid) is often instead called a "witness". But that is a technical term whose meaning in this context is not obvious from its colloquial meaning. —David Eppstein (talk) 06:58, 21 August 2026 (UTC)

The thing that’s confusing me is that the 2nd bullet point calls solutions “polynomial-length,” and says they can “solve the input,” as if they are an algorithm to fill in a sudoku grid, and the caption of the sudoku image calls solutions “easily verifiable,” as if they are filled-in sudoku grids.

I feel like the page should choose one meaning to use the word “solution,” and choose a different word for the other meaning. If “witness” is too technical, it could define it, use a different word, or choose the verifiable one to be “solution” and call the polynomial-length one “algorithm” or another word. SacrifycedStoat (talk) 08:17, 21 August 2026 (UTC)

The size of a filled-in sudoku grid is polynomial (in fact linear) in the size of the puzzle. The word "polynomial" just describes the growth rate of something (here one size against another); it does not carry any implication that the thing that is polynomial is the time of an algorithm. —David Eppstein (talk) 16:18, 21 August 2026 (UTC)

In the article I changed polynomial length to polynomial size to clarify that it is not a "length of time" and thus, hopefully, to not misdirect the reader into thinking about algorithms instead of witnesses. —Quantling (talk | contribs) 02:20, 22 August 2026 (UTC)