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$ ?
$\begingroup$
$\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 RicherbyCommented Jun 23, 2016 at 8:32
-
$\begingroup$ Possible duplicate. This one has some examples, too. $\endgroup$– RaphaelCommented 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$– RaphaelCommented Jun 23, 2016 at 9:26
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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).
answered Jun 23, 2016 at 8:30