10
$\begingroup$

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?

$\endgroup$
5
  • 4
    $\begingroup$ I think you should consider posting questions about NP-completeness on cstheory.stackexchange.com instead. $\endgroup$
    – Nate Eldredge
    Commented Jan 6, 2015 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
    Commented Jan 6, 2015 at 10:54
  • 16
    $\begingroup$ NP completeness is also on-topic here at MO. $\endgroup$
    – Joel David Hamkins
    Commented Jan 6, 2015 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
    Commented Jan 7, 2015 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
    Commented Jan 7, 2015 at 18:43

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .