1
$\begingroup$

I'm having trouble showing that $P\neq R$. Obviously $P\subseteq R$, but is there a decidable language which is definitely not (under all answers to open questions s.t. $P=NP$ or $NP=PSPACE$) in $P$ ?

$\endgroup$
3
  • 1
    $\begingroup$ Please don't ask a question in the title whose answer is the exact opposite of question in the body ("No" and "Yes", respectively). $\endgroup$ Jun 23, 2016 at 8:32
  • $\begingroup$ Possible duplicate. This one has some examples, too. $\endgroup$
    – Raphael
    Jun 23, 2016 at 9:24
  • $\begingroup$ In reply to @adrianN, I found both questions by googling "problems not in P" and following some links. $\endgroup$
    – Raphael
    Jun 23, 2016 at 9:26

1 Answer 1

8
$\begingroup$

Yes, there are decidable languages that are definitely not in P. The time hierarchy theorem says that P$\,\neq\,$EXP, so P$\,\neq\,$R, independently of the P vs NP problem. Any EXP-complete problem is definitely not in P: for example determining whether white has a winning strategy from a position in generalized chess ("generalized" in the sense of allowing a board of any dimensions, with any arrangement of any number of pieces, but otherwise following all the rules of standard chess).

$\endgroup$

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.