Jump to content

Talk:Complete (complexity)

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

This is the current revision of this page, as edited by Cewbot (talk | contribs) at 22:02, 30 January 2024 (Maintain {{WPBS}} and vital articles: 2 WikiProject templates. Create {{WPBS}}. Keep majority rating "Stub" in {{WPBS}}. Remove 2 same ratings as {{WPBS}} in {{WikiProject Mathematics}}, {{WikiProject Computer science}}. Remove 1 deprecated parameter: field.). The present address (URL) is a permanent link to this version.

(diff) ← Previous revision | Latest revision (diff) | Newer revision → (diff)

Untitled[edit]

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)[reply]