Talk:List of NPcomplete problems
This article is of interest to the following WikiProjects:  

Protein Folding[edit]
What about protein folding? —Preceding unsigned comment added by 129.11.60.53 (talk) 16:11, 8 March 2008 (UTC)
 What about it? If you want a proof that it's hard to do: http://www.cs.berkeley.edu/~christos/hp.ps 134.58.42.46 (talk) 12:37, 1 December 2010 (UTC)
Betweenness problem[edit]
The Betweenness problem, as defined in the article has a polynomial algorithm and therefore is in P. If it were an NPComplete problem than P=NP. I think that there is a problem with the definitions, and the one that added the betweenness problem meant to other definition. Until the correct definition is found, I'll remove the problem from the list. APH 07:26, 30 May 2005 (UTC)
 It does belong and should be added back; see SJ. Opatrny, Total ordering problem, SIAM J. Comput., 8 (1979), pp. 111–114. Problem is MS1 in Garey, M. R.; Johnson, D. S. (1979), Computers and Intractibility: a guide to the theory of NPcompleteness, W.H. Freeman, according to http://acawiki.org/Total_ordering_problem Jodi.a.schneider (talk) 09:25, 5 October 2010 (UTC)
 I no longer see betweenness on the list so I guess it was removed at some point, but it does belong (with the link JAS gave), and now has its own article; I will add it back. —David Eppstein (talk) 02:10, 20 August 2015 (UTC)
Vertex Covering[edit]
Google only finds the phrase "Covering by vertex cover" on this page, so I don't think that it is distinct from Vertex Cover. I removed it as a duplicate. James Aguilar 17:11, 29 November 2005 (UTC)
Copyright issues[edit]
According to Ideaexpression divide:
 If the book lists only facts, one might say that it is not original, but if the facts are selected and arranged in an original manner, the book may be copyrighted.
I've read elsewhere of an example where a book of recipes was copied and the copyright owner sued. The defendant claimed that the recipes were wellknown simple lists of items not subject to copyright, but because the work copied even the organization and page numbering of the original, it was found to be in infringement.
Although I think "List of NPcomplete problems" is an excellent article (especially as a source of new articles to write), I'm concerned that we may also be vulnerable to claims of copyright violation because we essentially steal the NP Guide's presentation. Maybe I should post to Wikipedia: Copyright problems and see if they can decide if this is an issue? What do the original contributors think? Thanks. Deco 05:46, 28 November 2005 (UTC)
 I took a course based on Garey & Johnson and the first thing I thought on seeing this article is that it's awfully close the the appendix of that book. I compared it with the actual book and, cosmetics aside, it's the same list organized in the same way, with the only difference being that G&J include descriptions of each problem. I not sure that it's definitely is a COPYVIO but the publishers could probably make a good case for it if they wanted to. In addition, given that the G&J is 30+ years old, the list severely needs to be updated anyway. I'd propose the following changes:
 Remove the red links. Most of the problems in the list are from journal articles and probably don't meet WP notability guidelines, so it doesn't make sense to list them individually anyway.
 Remove the organization and list the articles alphabetically. If people then want to reorganize it without referring to G&J or previous versions of the article. Then no one can complain that we're using G&J's organization.
 If there are no objections I'll go ahead and make these changes in a few days. The COPYVIO process is painful and since the issue is borderline it would be better to resolve it with a few edits. RDBury (talk) 00:18, 4 August 2013 (UTC)
Have youall considered the possibility that the book's appendix is a copy of our article? I found that such a reverseCopyright violation had occurred in another article when someone suggested that a section of the article was a copy of part of a book. It turned out that the section in our article (the actual text which was alleged to be a copy) was older (by our revision history) than the book.JRSpriggs (talk) 09:51, 4 August 2013 (UTC) The book was published, with its appendix, in 1979. —David Eppstein (talk) 16:13, 4 August 2013 (UTC)
Longest common subsequence[edit]
Is LCS NPComplete problem? I think, that there exists simple polynomial algorithm, which solves this problem. Doesn't it? longest_common_subsequence
I was wondering the same thing, there is a linear dynamic programming algorithm to solve the LCS problem.
 It is NPcomplete in the general case of any number of input strings, not just two. Google is your best friend. Articles must be updated. Unfortunately I have no time now. mikka (t) 20:14, 27 March 2006 (UTC)
 No it's not. If you have strings of length , then you can find the longest subsequence common to all of them with a Dynamic Programming algorithm that takes time. This is polynomial in the input length. I've removed the link to LCS (besides, that article is a big mess, and doesn't even make mention of this strings problem.) Shreevatsa 05:55, 7 May 2006 (UTC)
 Shreevatsa, could you give a reference to that algorithm. There must be some hidden exponent, which is constant or even 1 for your setting. I took a look at the paper [1] and it has a very reasonable reduction from vertex cover to LCS. GrGr 11:02, 4 July 2006 (UTC)
 I was wrong; I shouldn't have spoken without thinking it through. I couldn't get at that paper, but I tried to recall the algorithm I had in mind, and it is something entirely different (solves the longest common substring problem, for which of course, there are much better solutions than that). Sorry about that. (Which means I don't have a polynomialtime solution for the NPcomplete problem? How shocking!) :)
 At the same time, I think that it's not a good idea to link to the LCS page unless it mentions this (several strings) version. Shreevatsa 13:01, 11 July 2006 (UTC)
 I agree, that linking to longest_common_subsequence is not a good idea, if the article does not mention the problem described in Garey & Johnson. If I have some time, maybe I will improve the LCS article. (Btw I think, it would have been more shocking, if you actually had a polynomialtime algorithm :)) GrGr 14:09, 11 July 2006 (UTC)
 Yeah, ideally longest common subsequence would mention both variants and then we could link it (with an appropriate note attached). But that'll take a bit of effort. Deco 17:46, 11 July 2006 (UTC)
 I agree, that linking to longest_common_subsequence is not a good idea, if the article does not mention the problem described in Garey & Johnson. If I have some time, maybe I will improve the LCS article. (Btw I think, it would have been more shocking, if you actually had a polynomialtime algorithm :)) GrGr 14:09, 11 July 2006 (UTC)
 Shreevatsa, could you give a reference to that algorithm. There must be some hidden exponent, which is constant or even 1 for your setting. I took a look at the paper [1] and it has a very reasonable reduction from vertex cover to LCS. GrGr 11:02, 4 July 2006 (UTC)
 No it's not. If you have strings of length , then you can find the longest subsequence common to all of them with a Dynamic Programming algorithm that takes time. This is polynomial in the input length. I've removed the link to LCS (besides, that article is a big mess, and doesn't even make mention of this strings problem.) Shreevatsa 05:55, 7 May 2006 (UTC)
On harderthanNP problems[edit]
Someone needs to go through and remove all of the PSPACEcomplete, EXPTIMEcomplete, etc. problems; I have created List of PSPACEcomplete problems to store the former. It might be desirable to also have List of EXPTIMEcomplete problems. So far I have only done the Games and Logic sections; I don't know that much about the rest (and probably made mistakes even in those sections). Ben Standeven 08:29, 30 January 2007 (UTC)
Finite state automata intersection not in NP[edit]
The page claims that "intersection of finite state automata" is NPcomplete. I assume that this refers to the question whether or not such an intersection is empty. But this claim appears to be unfounded. For a fixed number of automata (such as 2), the problem is clearly in PTIME: just construct the intersection automaton. For polynomial number of automata, one can find an algorithm running in PSPACE: "guess" an accepted word letter by letter, show acceptance, and use Savitch's theorem to reduce NPSpace to PSpace. Indeed, this problem is reported to be PSPACEcomplete in various sources:
 The paper "PSPACEcompleteness of Modular Supervisory Control Problems" (PS) states that the problem is PSpace complete, citing the following related sources:
 D. Kozen. Lower bounds for natural proof systems. In Proc. 18th Symp. on the Foundations of Computer Science, pages 254–266, 1977.
 M.R. Garey and D.S. Johnson. Computers and Intractability: A Guide to the Theory of NPCompleteness. W.H. Freeman, 1979.
 K.J. Lange and P. Rossmanith. The emptiness problem for intersections of regular languages. In I. Havel, editor, Proc. of the 17th Conf. on Mathematical Foundations of Computer Science, number 629 in LNCS, pages 346–354. SpringerVerlag, 1992.
 List of PSPACEcomplete problems lists the problem with a question mark (which should probably be removed)
 http://www.cs.mun.ca/~harold/Courses/Old/Ling6800.W06/Diary/index.html states that "Finite State Automata Intersection is PSPACEcomplete (Garey and Johnson (1979), Problem AL6, p. 266)" where the cited source is "Garey, M.R., and Johnson, D.S. (1979) Computers and Intractability: A Guide to the Theory of NPCompleteness. W.H. Freeman; San Francisco, CA."
I thus removed automata intersection from the article. Markus Krötzsch 09:33, 26 March 2007 (UTC)
 You are absolutely right. I can reassure you that DFA intersection emptiness is PSPACEcomplete, proved in (Kozen, 1977). Some introductory textbooks contain the fact that the problem is NPhard (as exercise or theorem with proof), so possibly someone simply missed the difference between hardness and completeness. Hermel (talk) 22:08, 10 October 2008 (UTC)
 Hermel, could you please list sources that say that the intersection emptiness problem is NPhard because I was unable to find any. — Preceding unsigned comment added by Mikew72324 (talk • contribs) 22:35, 15 August 2011 (UTC)
Permuatation Flow shop problem[edit]
I'm looking at this problem for some work I'm doing and it is npcomplete for more than 2 machines. I don't know if it is in the list under another name, but if not, it could be added to the list. Just a thought. —Preceding unsigned comment added by 71.63.82.192 (talk) 07:16, 24 September 2007 (UTC)
Games[edit]
The games section needs more explanation as to what part of the game is NPComplete. For example, is the problem with Sudoku to find the possible number of solved puzzles, the possible number of solvable puzzles, or what? The Sudoku article mentions nothing about NPCompleteness (which is another thing, these things should all be mention in their respective articles). Asmeurer (talk ♬ contribs) 18:26, 16 November 2008 (UTC)
 The problem with Sudoku is to test whether a particular nbyn (rather than 9by9) puzzle can be completed to a solution. However, NPcompleteness is a bit of an issue because the usual reductions involve problems that may have multiple solutions while Sudoku puzzles are generally required to have exactly one. There's a workaround involving Valiant and Vazirani, "NP is as easy as detecting unique solutions" but it involves randomized Turing reductions rather than the usual manyone reductions. —David Eppstein (talk) 18:41, 16 November 2008 (UTC)
That's great. You should put that in this article/the sudoku article. I would do it, but I only understand about half of what you wrote, and I would either screw it up or have to copypaste verbatim. Asmeurer (talk ♬ contribs) 05:26, 17 November 2008 (UTC)
 I don't have time to work on this tonight, but in case anyone else wants to take a crack, I wrote more on this three years ago on my blog (usual disclaimers about reliable sources and original research go here). —David Eppstein (talk) 05:53, 17 November 2008 (UTC)
Someone should indicate that the problem of finding a purestrategy Nash equilibrium is NPcomplete; I don't see that problem on this list. ~Phil —Preceding unsigned comment added by 66.28.35.109 (talk) 20:00, 14 October 2009 (UTC)
 If each player has n choices, there are only n^2 pure strategy pairs to check, and each can be checked in linear time, so it's in P. Finding a mixed strategy equilibrium is also in P, using linear programming. I vaguely recall there was some related problem that was difficult (maybe finding ALL mixed strategy equilibria?) —Preceding unsigned comment added by 75.173.217.183 (talk) 06:26, 19 November 2010 (UTC)
I agree that some need some clarification. You're right on the sudoku one though, David. I'm a little curious about the Super Mario Bross one. What aspect of that one is NPcomplete. I suspect it may only be on the list due to some vandalism.128.187.80.2 (talk) 23:10, 2 April 2013 (UTC)
 I checked the source for SMB and it seems legit. An instance of a 'problem' consists of a level, i.e. platforms, obstacles, etc. The question is whether it's possible for Mario to get from the start of the level to the end. The authors claim that certain other Nintendo games are NPhard. RDBury (talk) 03:12, 8 August 2013 (UTC)
Steiner tree[edit]
many of the problem titles in the section "spanning trees" which had no page seemed to be asking for the article []Steiner tree]] so I have directed them there. I am not certain that this is the best practice, but deleting them would likely lead to more confusion, and them being readded later. Jasen betts (talk) 10:02, 3 September 2009 (UTC)
References[edit]
Many of the problems in this list have no clear meaning. It seems that a prerequisite for listing a problem here should be a reference: to a peerreviewed paper, to a book, or at least to a wikipedia article. —Preceding unsigned comment added by 132.64.44.156 (talk) 05:42, 15 August 2010 (UTC)
Concerning the comment in the main article ("This article includes a list of references, related reading or external links, but its sources remain unclear because it lacks inline citations.") and the comment above: Garey & Johnson is cited repeatedly in the main article and provides definitions to all of the problems listed. Anyone familiar with computer science would know to go to this book (the most cited book in all of computer science). Rather than citing G&J for every problem listed, the article provides a "covering citation" at the front of the list referring the reader to G&J's comprehensive listing. Dan Suthers (talk) 10:04, 1 December 2011 (UTC)
Actual reductions[edit]
Is there a website that features reductions used to prove hardness results, possibly using some graphical representation (i.e. edgepartitioning a graph is hard by reduction from 3SAT, which could be visualized by assigning vertex A to the former problem, vertex B to the latter, and directing an edge from B to A)? 134.58.42.46 (talk) 15:20, 20 October 2010 (UTC)
Nontrivial greatest common divisor[edit]
Nontrivial greatest common divisor links to Greatest common divisor of integers, which is clearly not nphard. Euclids algorithm is a simple well known polynomial algorithm to compute the gcd. This should be clarified or removed from the list. — Preceding unsigned comment added by 46.14.248.115 (talk) 12:17, 20 December 2011 (UTC)
Shortest path computation[edit]
It can be solved by Dijsktra's algorithm which runs in polynomial time. So was is it listed as an NPcomplete problem?2001:760:3403:FFFC:2C63:181F:461E:6DE3 (talk) 15:44, 18 February 2013 (UTC)
Quadratic Polynomials[edit]
I find this NPcomplete problem to be of a different flavor than others listed here. I think it should be included. It is discussed in the paper by Manders and Adelman, "NPcomplete decision problems for Quadratic Polynomials".
The problem is incredibly simple. Given positive integers . Find positive integers such that .
 I think it's rather . If , , which is immediate. If , , which is immediate. If , and . Morever, if y is positive, the problem is around , which is not NPcomplete. If y can be negative, I think the problem is more difficult than NPcomplete as the entries are infinite. Ftiercel (talk) 16:28, 9 November 2016 (UTC)
 Since this was recently (2019) added again, it is worth pointing out that Ftiercel's comments here are totally wrong: the numbers are exponential in the size of the input, so the naive algorithm implied by Ftiercel's comment runs in exponential time. (To say nothing of ignoring what appears to be the perfectly valid citation that accompanied the addition.) JBL (talk) 14:53, 6 December 2019 (UTC)
Games and Puzzles (Sudoku)[edit]
The statement currently in the list: "Testing whether a solved n × n Sudoku puzzle has a second solution." doesn't make sense to me and does not seem to match conclusions in the references. A discussion is here: User talk:David Eppstein. (I can move the discussion to this page if it is better). Thanks to anyone able to provide advise.—LithiumFlash (talk) 05:30, 9 April 2017 (UTC)
 LithiumFlash, the sentence in question both makes perfect sense and agrees with what is written in the reference. JBL (talk) 13:39, 10 April 2017 (UTC)
 JBL, That's fine. I'm not going to work on this list anymore. Just to let you know "Testing whether a solved n × n Sudoku puzzle has a second solution" does not make sense because a proper Sudoku never has more than one solution. Not as a puzzle, and not in its solved state (references can be found at the articles about Sudoku). Also, please be advised that other references were included with this entry, but were removed, which I believe is in contradiction to the policy on Wikipedia:Conflicting sources. For more on this topic please see User talk:David Eppstein.—LithiumFlash (talk) 14:13, 10 April 2017 (UTC)
 Yes, I have read that discussion  everything David Eppstein and EEng have said there looks correct to me, including the fact that the sources you're adding do not seem to meet Wikipedia's standards for reliable sources. JBL (talk) 16:16, 10 April 2017 (UTC)
 Do you stand by the statement "Testing whether a solved n × n Sudoku puzzle has a second solution." is worded correctly for an entry in "List of NPcomplete problems"?—LithiumFlash (talk) 16:31, 10 April 2017 (UTC)
 I think it is both completely understandable and supported by a citation to a published paper. It doubt it would be hard to come up with a phrasing that is correct and didn't bother your sensibilities, but to do so would require a greater respect for sourcing than you seem to have, and perhaps a better understanding of the relevant mathematics. JBL (talk) 18:25, 10 April 2017 (UTC)
 Thank you. Here is some material for consideration (below). I'll let you and other editors decide if the entry in List of NPcomplete problems should be revised. Of course you and others are also welcome to ammend or update the related knowledge in Sudoku and Mathematics of Sudoku. It won't bother me to see any of it changed (it was not me who placed the related statements in those articles). My only interest is that the text is supported by reliable sources.
 Thank you for your support.—LithiumFlash (talk) 18:53, 10 April 2017 (UTC)
 I think it is both completely understandable and supported by a citation to a published paper. It doubt it would be hard to come up with a phrasing that is correct and didn't bother your sensibilities, but to do so would require a greater respect for sourcing than you seem to have, and perhaps a better understanding of the relevant mathematics. JBL (talk) 18:25, 10 April 2017 (UTC)
On TSP problems categorization[edit]
Aren't you think that Traveling salesman problem & Bottleneck traveling salesman problem must be in Graphs and hypergraphs category?!! — Preceding unsigned comment added by 41.248.23.77 (talk) 13:35, 8 July 2017 (UTC)
Art Gallery Problem[edit]
The Art Gallery Problem was removed altogether from this article. This might be an easy solution, but I don’t find the article sufficiently informative this way.
Because there is a common misconception, that the standard version is NPcomplete, it would be better to clarify which version is and which versions are not NPcomplete.
My suggestion looks like this:
Art Gallery Problem with vertex guards (Other versions  where the placement of guards is allowed anywhere in the polygon or on the boundary  are ExiatentialReal complete <insert link to the article Existential theory of the reals>)
I can’t provide a citation that the vertex guard version is not only NPhard but also compete, because in older publications all versions are falsely labelled as NPcomplete. And to anyone in the field it is clear, that this problem is in NP, if you only allow vertex guards. Can anyone back me on this or should I explain it quickly?
Also could someone else please post that edit if agreed upon? JRellek (talk) 23:58, 17 December 2019 (UTC)
 This is a list of NPcomplete problems, not a list of problems that are complete for other classes that are hard for NP. It is indeed clear that it is in NP if you only allow vertex guards (you just have to cover all of the polynomially many regions of the visibility diagram of the candidate guard locations) but to include something like that we still need a source. Another problem here is that our art gallery article says nothing about NPcompleteness of any variant. I think that problems listed here should go into more detail about the complexity in the linked article, and that is not currently true for this one. (It does discuss existsRcompleteness and NPhardness, but not NPcompleteness.) —David Eppstein (talk) 01:05, 18 December 2019 (UTC)
String to String correction is not NPcomplete[edit]
Converting any string to another is Polytime. (https://en.wikipedia.org/wiki/Levenshtein_distance) There is an extended version of the problem ( https://dl.acm.org/doi/10.1145/800116.803771 ) but the linked page (https://en.wikipedia.org/wiki/Stringtostring_correction_problem) only mentions the standard problem. Suggestion>> Change the link to a stub extended string to string problem page with the reference (https://dl.acm.org/doi/10.1145/800116.803771)
R1CS constraint system[edit]
I would like to add R1CS constraint system to the list. what do you think? Jackzhp (talk) 11:32, 14 March 2021 (UTC)
Solving twovariable quadratic polynomials over the integers[edit]
This is included in the list but I think it is wrong. I'm not sure about this but what is NPComplete is the decision version, otherwise factoring should also be NPcomplete (which most likely is not) as solving second degree Diophantine equations is equal to factoring. Alperen (talk) 17:21, 11 February 2023 (UTC)