0
$\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$ – David Richerby Jun 23 '16 at 8:32
  • $\begingroup$ Possible duplicate. This one has some examples, too. $\endgroup$ – Raphael Jun 23 '16 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 '16 at 9:26
7
$\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, privacy policy and cookie policy

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