Talk:List of NP-complete problems
From Wikipedia, the free encyclopedia
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)
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)
Contents |
[edit] 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)
[edit] 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(m2k) 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)
- 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)
- 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 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(m2k) 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)
[edit] 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)
[edit] 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)
