I believe that I discovered a method to generate several NP-complete problems. The NP-completeness proof is not immediately apparent to me. I did not find any reference in complexity literature to my problems and their $NP$-completeness. Such problems include the following posts:

How hard is reconstructing a permutation from its differences sequence?

Recognizing sequences sortable by transpositions?

Is it fine to post question asking for proofs of $NP$-completeness of several problems?

  • 4
    $\begingroup$ I think you should consider posting questions about NP-completeness on cstheory.stackexchange.com instead. $\endgroup$ – Nate Eldredge Jan 6 '15 at 7:52
  • 4
    $\begingroup$ Upvoted since this is a reasonable question to ask; I have no specific opinion on the subject itself. $\endgroup$ – user9072 Jan 6 '15 at 10:54
  • 16
    $\begingroup$ NP completeness is also on-topic here at MO. $\endgroup$ – Joel David Hamkins Jan 6 '15 at 15:06
  • 2
    $\begingroup$ Even if a question is on-topic in more than one site, choose just one site and ask it there. Which site do you think is more likely to have experts that can contribute toward an answer? $\endgroup$ – Gerald Edgar Jan 7 '15 at 17:19
  • 1
    $\begingroup$ @GeraldEdgar Both sites have experts on computational complexity. Usually, I first post on TCS SE and offer a bounty. Then I post on mathOverflow if I did not get a satisfying answer. Sometimes, such as the first example above, a post generates more interest among mathOverflow members. $\endgroup$ – Mohammad Al-Turkistany Jan 7 '15 at 18:43

You must log in to answer this question.

Browse other questions tagged .