File talk:P np np-complete np-hard.svg

This is wrong.

You imply in this diagram that all P problems would be NP-hard if P = NP, but this is false. AC0 problems would certainly not be NP-hard, and there's no reason to think that any problem not known to be P-hard would be NP-hard. Twin Bird (talk) 23:06, 23 July 2011 (UTC)

NP-hard is usually defined with respect to polynomial time reductions. So if P = NP, then the reducing machine can solve NP-complete problems. Thus it can reduce 3SAT to a very easy problem, such as problems in AC⁰. Thus P = NP will imply that problems in AC⁰ are NP-hard. --Robin (talk) 23:53, 23 July 2011 (UTC)

RobinK is correct. Dcoetzee 05:35, 24 December 2011 (UTC)

The right diagram is wrong. If P = NP, P is not equal to NP-complete. That is because the trivial decision problems (the problem that always returns true, and the problem that always returns false; i.e. problems that emit no information) are obviously in P but are not reducible from any problems that may return both true and false (I am assuming many-one reduction here). Thus, they are not in NP-hard, and thus not in NP-complete. --208.80.119.68 (talk) 22:41, 22 February 2012 (UTC)

Still wrong, but for a different reason: NPH and NPC do not admit the trivial languages, while P and NP do... — Preceding unsigned comment added by 173.77.144.116 (talk) 09:42, 19 February 2012 (UTC)

By definition, P and NP-Complete are both *subsets* of NP. Also by definition, some NP-Complete problems are a subset of NP-Hard problems. Behnam (talk) 02:50, 17 July 2012 (UTC)

AFAIK I also agree. AFAIK the diagram is wrong. Certainly if P=NP is true; it is not true that P=NPC. NPC would be always a proper subset of NP. Mariostorti (talk) 11:52, 4 September 2012 (UTC)

Mariostorti, would you like to give a reference for your assumption "NPC being always a proper subset of NP"? — Preceding unsigned comment added by Behnam (talk • contribs) 22:14, 6 November 2012 (UTC)

Proof: take the empty language Ø, a problem in P. No other language can ever be reduced to Ø, because yes-instances of that problem cannot be mapped to yes-instances of Ø. Therefore, Ø can never be in NPC because that would be every other language in NP could be reduced to it. — Preceding unsigned comment added by 83.84.61.92 (talk) 21:45, 29 June 2014 (UTC)

Similarly, Σ* cannot be **NP**-complete, since it has no no-instances. Dricherby (talk) 17:16, 31 January 2016 (UTC)

A Similar Diagram

The book Algorithms (by Umesh Vazirani) has a similar diagram to the first part of this one on page 260 (chapter 8). Behnam (talk) 02:50, 17 July 2012 (UTC)