Talk:Complete (complexity)

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Mathematics (Rated Stub-class, Low-priority)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
Stub Class
Low Priority
 Field: Discrete mathematics
WikiProject Computer science (Rated Stub-class, Mid-importance)
WikiProject icon This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Stub-Class article Stub  This article has been rated as Stub-Class on the project's quality scale.
 Mid  This article has been rated as Mid-importance on the project's importance scale.
 

It seems to me that the sentence

For example, NP, co-NP, PLS, PPA all have complete problems, while RP, ZPP, BPP and TFNP do not have complete problems.

is not known to be true. If it were true, then we'd know that BPP is not P, for example. 18.241.3.124 (talk) 03:40, 13 December 2007 (UTC)