<p>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). </p>

<p>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. </p>

CC BY-SA 3.0
2013-08-08T14:42:05.340Z
Thank you, Peter, for trying to help me. I will try to LOGSPACE reduce Multiple Sequence Alignment (MSA) from NP-complete to P-complete.
Garo Garabedyan
CC BY-SA 3.0
2013-08-08T18:39:54.800Z
Nice answer. Motivated me to post a question. http://cstheory.stackexchange.com/questions/18587/is-finding-logspace-reductions-harder-than-p-reductions
Mohammad Al-Turkistany
CC BY-SA 3.0
2013-08-10T14:07:48.460Z
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?
Tayfun Pay
CC BY-SA 3.0
2013-08-08T12:56:01.693Z
2013-08-08T13:48:45.797Z
2013-08-08T13:48:45.797Z
Peter Shor 
<p>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.</p>

CC BY-SA 3.0
2013-08-11T15:58:30.843Z
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.
Garo Garabedyan
CC BY-SA 3.0
2013-08-11T21:06:32.490Z
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.)
Peter Shor 
CC BY-SA 3.0
2013-08-12T11:31:13.513Z
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".
David Richerby
CC BY-SA 3.0
2013-08-10T08:24:43.547Z
2013-08-10T08:24:43.547Z
David Richerby
<p>Where are exactly NP-complete problems if P=NP? 
They will be definitely in P, but will they be P-complete?</p>

CC BY-SA 3.0
2013-08-08T07:49:10.380Z
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
Garo Garabedyan
CC BY-SA 3.0
2013-08-09T07:17:31.760Z
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/on-topic] for more information on what is meant by this. cstheory is a Q&A site, not help request forum.
Kaveh
<cc.complexity-theory><np-complete>
Where are NP-complete problems if P=NP
Garo Garabedyan
# Where are NP-complete problems if P=NP

(Asked by: username_0 on 2013-08-08)

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

**Tags:** cc.complexity-theory, np-complete
> **Comments:**
> **username_0**: 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  
> **username_1**: 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/on-topic] for more information on what is meant by this. cstheory is a Q&A site, not help request forum.  

---

## 2 answers

### Answer by username_2 on 2013-08-08. Score: 17

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.

> **Comments:**
> **username_0**: Thank you, Peter, for trying to help me. I will try to LOGSPACE reduce Multiple Sequence Alignment (MSA) from NP-complete to P-complete.  
> **username_3**: Nice answer. Motivated me to post a question. http://cstheory.stackexchange.com/questions/18587/is-finding-logspace-reductions-harder-than-p-reductions  
> **username_4**: 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?  

---

### Answer by username_5 on 2013-08-10. Score: 1

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.

> **Comments:**
> **username_0**: 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.  
> **username_2**: 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.)  
> **username_5**: 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".  

---

