How can we find the list of open problems on $NP$-comlpete?


closed as not a real question by Kaveh Feb 6 '11 at 23:46

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 10
    $\begingroup$ Do you mean a list of NP problems which are not known to be in P nor to be NP-complete? If so, this topic is an exact duplicate of Problems Between P and NPC. $\endgroup$ – M.S. Dousti Jan 1 '11 at 15:21
  • 9
    $\begingroup$ It's difficult to tell what is being asked here. This question is ambiguous and vague, and without clarification cannot be reasonably answered in its current form. I am voting to close as "not a real question". $\endgroup$ – Kaveh Jan 2 '11 at 6:05
  • 3
    $\begingroup$ You can try the NP-Completeness columns: www2.research.att.com/~dsj/columns. But I agree, this question is just too vague. Perhaps it can be rephrased as a reference request to a survey or something. $\endgroup$ – Aryabhata Jan 2 '11 at 9:20
  • 1
    $\begingroup$ misagh, I closed this question because it is not clear what you are asking for and you have not replied to the comments after a month. We can reopen the question if you clarify it, just clarify it and then flag it for moderator attention. Thanks. $\endgroup$ – Kaveh Feb 6 '11 at 23:48

you can also find some other problems in http://garden.irmacs.sfu.ca/?q=category/theoretical_computer_science

  • 7
    $\begingroup$ Edit your previous answer instead adding new answers. $\endgroup$ – Saeed Jan 1 '11 at 15:57
  • $\begingroup$ @Saeed: Although I upvoted your comment, after thinking about it again, I am not sure if I agree. There are cases where posting two answers separately is acceptable. Although the user 3008 could have edited the older answer, I do not know why he/she should have done so or anyone could order him/her to do so. $\endgroup$ – Tsuyoshi Ito Jan 2 '11 at 13:10
  • $\begingroup$ @Tsuyoshi Ito 伊藤剛志, yes may be if I said it's better to ... was better (but is not normal in QA sites), but if anyone wants to show his/her force to create new answer,I think he/she will downvote this answer. In this case I think user 3008 can edit answer and add too many item, I think user 3008 didn't see edit button. $\endgroup$ – Saeed Jan 2 '11 at 14:49

you can find some open Np-complete problem at the end of "computer and intractability" (Garey & Johnson)

  • 3
    $\begingroup$ -1: That is an old list. $\endgroup$ – Aryabhata Jan 3 '11 at 2:55

Not the answer you're looking for? Browse other questions tagged or ask your own question.