0
$\begingroup$

I am a CS student. I am looking at some questions my professor made and I got stuck in this one.
"Which one of the following inclusions between complexity classes is coherent with the current knowledge? (even if not proved, yet)". The possible answers are:

  • P $\subseteq$ EXP (Which I know it is true)
  • NP $\subseteq$ EXP (Which I know it is also true)
  • EXP $\subseteq$ P (Which is clearly false)
  • EXP $\subseteq$ NP

Now, if I flag as correct answers only the two I know that are true, I obtain that my answer is partially correct. So in conclusion my question is: Given the current knowledge can we say that EXP $\subseteq$ NP or is this just a mistake of my professor?
Thank you for your answers!

Improve this question
$\endgroup$
2
  • $\begingroup$ I assume the word should be "consistent" and not "coherent". $\endgroup$
    – gnasher729
    Jul 7, 2022 at 11:08
  • $\begingroup$ The forth question is IMO neither proven to be true or false; I would bet that it is false - there should be exponential time problems where instances with an answer "yes" cannot be solved by making a lucky guess for a proof of the "yes" answer that can be verified in polynomial time. $\endgroup$
    – gnasher729
    Jul 7, 2022 at 11:11

1 Answer 1

Reset to default
4
$\begingroup$

Notice that the question is not asking for inclusions that are known to be true, but instead just for those that could conceivably be true given the current knowledge. In other words you need to select both the relations that are already known to be true and the relations whose status is still unknown.

The inclusion $\mathsf{EXP} \subseteq \mathsf{NP}$ is not disproven since, from what we know so far, it could be the case that $\mathsf{EXP} = \mathsf{NP}$. Therefore the last option should also be marked.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Question: Which instances can be solved by making a lucky guess at a proof for the correct answer, and verifying the proof in polynomial time? NP: All instances with answer "Yes", possibly some others. co-NP: All instances with answer "No", possibly some others. EXP: Possibly none or few, but impossible for me or someone more clever to prove. $\endgroup$
    – gnasher729
    Jul 7, 2022 at 11:15

Your Answer

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

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