-2
$\begingroup$

Where are exactly NP-complete problems if P=NP? They will be definitely in P, but will they be P-complete?

$\endgroup$
2
  • 1
    $\begingroup$ Allow me to clarify my question. It is about where exactly are NP-complete problems if P=NP. They will be definitely in P, but will they be P-complete? -Garo $\endgroup$ Aug 8 '13 at 7:49
  • $\begingroup$ Welcome to cstheory, a Q&A site for research-level questions in theoretical computer science (TCS). Your question does not appear to be a research-level question in TCS. Please check the help center for more information on what is meant by this. cstheory is a Q&A site, not help request forum. $\endgroup$
    – Kaveh
    Aug 9 '13 at 7:17
17
$\begingroup$

Most NP-complete problems are NP-complete under LOGSPACE reductions; that is, you can take an arbitrary problem in NP, and using a LOGSPACE algorithm, reduce it to your problem. Any NP-complete problem under LOGSPACE reductions will also be P-complete under LOGSPACE reduction, even if P=NP, as you can use the same procedure to reduce a P-complete problem to your problem with a LOGSPACE reduction (since P $\in$ NP).

Some problems are only NP-complete under P reductions. In this case, it is not clear whether or not they are P-complete. I don't know of any NP-complete problems which are not also known to be P-complete, but I haven't tried searching to see whether anybody has investigated this.

$\endgroup$
3
  • 3
    $\begingroup$ Thank you, Peter, for trying to help me. I will try to LOGSPACE reduce Multiple Sequence Alignment (MSA) from NP-complete to P-complete. $\endgroup$ Aug 8 '13 at 14:42
  • 1
    $\begingroup$ Nice answer. Motivated me to post a question. cstheory.stackexchange.com/questions/18587/… $\endgroup$ Aug 8 '13 at 18:39
  • $\begingroup$ What is as an example of a NP-complete problem that is NP-complete under P reductions but not knowing to be NP-complete under L reductions? $\endgroup$
    – Tayfun Pay
    Aug 10 '13 at 14:07
1
$\begingroup$

P=NP means that the two classes are the same in every possible way (because they're the same class). In particular, it means they have exactly the same set of complete problems.

$\endgroup$
3
  • $\begingroup$ Thank you, David, for answering the quesiton. Allow me to share why I think that it is not so simple: if P=NP, P=NP=NP-complete and that is why I have doubts whether NP-complete problems will be P-complete (being both in P and in P-hard) or will be only in P, if P=NP. $\endgroup$ Aug 11 '13 at 15:58
  • 6
    $\begingroup$ This answer is correct if you're talking about NP-complete with respect to LOGSPACE reductions and P-complete with respect to LOGSPACE reductions. But usually, when we say NP-complete, we mean with respect to P reductions. If P=NP, all NP problems are NP-complete with respect to P reductions. (And all P problems are P-complete with respect to P reductions with no hypotheses.) $\endgroup$ Aug 11 '13 at 21:06
  • $\begingroup$ Good point and it's definitely useful to draw attention to the kind of reductions being used. Having said that, if P and NP are the same class, it would be strange to define completeness for that class in one way when we call the class "P" and another way when we call it "NP". $\endgroup$ Aug 12 '13 at 11:31

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