3
$\begingroup$

Is Co-NP in PSPACE? I think it should obviously be, but I just wanted to make sure. I can find that NP is in PSPACE in Internet, but not on Co-NP.

$\endgroup$
8
$\begingroup$

By the same reasoning that NP is in PSPACE, co-NP is in co-PSPACE. But co-PSPACE = PSPACE (you can just flip the answer), so co-NP is in PSPACE, too.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.