This file does not require a rating on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | |||||||||||||||||||||||||||||
|
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)
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)
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)
This file does not require a rating on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | |||||||||||||||||||||||||||||
|
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)
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)
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)