I am wondering if anyone knows if there are any NP-complete problems that are also known to be in IP (interactive polynomial time). I know problems like Graph Isomorphism are in IP, but such problems are not known to be NP-complete.

Moreover, if there were or were not an NP-complete problem in IP, what would be the consequences?


1 Answer 1


$$ IP = PSPACE $$ According to wikipedia. Thus $NP \subseteq IP$ and all NP-complete problems are in $IP$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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