Talk:List of NP-complete problems

Protein Folding

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

The Betweenness problem, as defined in the article has a polynomial algorithm and therefore is in P. If it were an NP-Complete 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 NP-completeness, 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

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

According to Idea-expression 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 well-known 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 NP-complete 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 re-organize 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 you-all considered the possibility that the book's appendix is a copy of our article? I found that such a reverse-Copyright 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

Is LCS NP-Complete 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 NP-complete 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 $k$ strings of length $m$, then you can find the longest subsequence common to all of them with a Dynamic Programming algorithm that takes $O(m^{2}k)$ 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 $k$ 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 polynomial-time solution for the NP-complete 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 polynomial-time 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)

On harder-than-NP problems

Someone needs to go through and remove all of the PSPACE-complete, EXPTIME-complete, etc. problems; I have created List of PSPACE-complete problems to store the former. It might be desirable to also have List of EXPTIME-complete 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

The page claims that "intersection of finite state automata" is NP-complete. 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 PSPACE-complete in various sources:

• The paper "PSPACE-completeness 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 NP-Completeness. 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. Springer-Verlag, 1992.
• List of PSPACE-complete 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 PSPACE-complete (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 NP-Completeness. 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 PSPACE-complete, proved in (Kozen, 1977). Some introductory textbooks contain the fact that the problem is NP-hard (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 NP-hard 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

I'm looking at this problem for some work I'm doing and it is np-complete 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

The games section needs more explanation as to what part of the game is NP-Complete. 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 NP-Completeness (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 n-by-n (rather than 9-by-9) puzzle can be completed to a solution. However, NP-completeness 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 many-one 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 copy-paste 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 pure-strategy Nash equilibrium is NP-complete; 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 NP-complete. 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 NP-hard. RDBury (talk) 03:12, 8 August 2013 (UTC)

Steiner tree

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 re-added later. Jasen betts (talk) 10:02, 3 September 2009 (UTC)

References

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 peer-reviewed 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

Is there a website that features reductions used to prove hardness results, possibly using some graphical representation (i.e. edge-partitioning 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)

Non-trivial greatest common divisor

Non-trivial greatest common divisor links to Greatest common divisor of integers, which is clearly not np-hard. 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

It can be solved by Dijsktra's algorithm which runs in polynomial time. So was is it listed as an NP-complete problem?2001:760:3403:FFFC:2C63:181F:461E:6DE3 (talk) 15:44, 18 February 2013 (UTC)

Quadratic Polynomials

I find this NP-complete 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, "NP-complete decision problems for Quadratic Polynomials".

The problem is incredibly simple. Given positive integers $A,B,C\geq 0$. Find positive integers $x,y$ such that $Ax^{2}+By-C=0$.

I think it's rather $A,B,C>0$. If $A=0$, $y={\frac {C}{B}}$, which is immediate. If $B=0$, $x={\sqrt {\frac {C}{A}}}$, which is immediate. If $C=0$, $x=0$ and $y=0$. Morever, if y is positive, the problem is around $O(min({\sqrt {\frac {C}{A}}},{\frac {C}{B}}))$, which is not NP-complete. If y can be negative, I think the problem is more difficult than NP-complete 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 ${\sqrt {\frac {C}{A}}},{\frac {C}{B}}$ 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)

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 NP-complete 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 NP-complete 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.

http://www-imai.is.s.u-tokyo.ac.jp/~yato/data2/SIGAL87-2.pdf

http://www-imai.is.s.u-tokyo.ac.jp/~yato/data2/MasterThesis.pdf

https://www.cs.wmich.edu/elise/courses/cs431/icga2008.pdf

http://geevi.github.io/2014/puzzles.html

https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3468838/

Thank you for your support.—LithiumFlash (talk) 18:53, 10 April 2017 (UTC)

On TSP problems categorization

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

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 NP-complete, it would be better to clarify which version is and which versions are not NP-complete.

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 NP-hard but also compete, because in older publications all versions are falsely labelled as NP-complete. 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 NP-complete 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 NP-completeness 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 exists-R-completeness and NP-hardness, but not NP-completeness.) —David Eppstein (talk) 01:05, 18 December 2019 (UTC)

String to String correction is not NP-complete

Converting any string to another is Poly-time. (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/String-to-string_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

I would like to add R1CS constraint system to the list. what do you think? Jackzhp (talk) 11:32, 14 March 2021 (UTC)

Solving two-variable quadratic polynomials over the integers

This is included in the list but I think it is wrong. I'm not sure about this but what is NP-Complete is the decision version, otherwise factoring should also be NP-complete (which most likely is not) as solving second degree Diophantine equations is equal to factoring. Alperen (talk) 17:21, 11 February 2023 (UTC)

The first sentence of this list article is "This is a list of some of the more commonly known problems that are NP-complete when expressed as decision problems." Does that address your concern? --JBL (talk) 18:50, 11 February 2023 (UTC)