The NP versus co-NP conjecture
Statement
A decision problem is in if its negation is in . A problem is NP-complete if it lies in and is -hard.
NP versus co-NP conjecture.
Hence, an -complete problem does not lie in .
This is another widely believed open conjecture in computational complexity, closely related to the asymmetry between efficiently verifiable yes and no answers.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.