1
$\begingroup$

It seems like $P\neq EXP$ is much easier than $P \neq NP$. How can I prove $P \neq EXP$?

(Well, after all I want to know any proof technique of proving there does not exist any algorithm of certain time complexity to prove a decision problem.)

It seems like we have to construct a problem where there's no way but to check all the cases which is exponential time...

$\endgroup$
0
$\begingroup$

I guess this is what you are looking for.

$\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.