-5

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

Kaveh
  • 21,577
  • 8
  • 82
  • 183
misagh
  • 59
  • 5
  • 10
    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. – Sadeq Dousti Jan 01 '11 at 15:21
  • 9
    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". – Kaveh Jan 02 '11 at 06:05
  • 3
    You can try the NP-Completeness columns: http://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. – Aryabhata Jan 02 '11 at 09:20
  • 1
    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. – Kaveh Feb 06 '11 at 23:48

2 Answers2

0

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

user3008
  • 12
  • 7
    Edit your previous answer instead adding new answers. – Saeed Jan 01 '11 at 15:57
  • @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. – Tsuyoshi Ito Jan 02 '11 at 13:10
  • @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. – Saeed Jan 02 '11 at 14:49
-2

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

user3008
  • 12