Let $L$ be a language in $NP$. Then are there any results on whether there exists a polynomial-time algorithm (polynomial in the length of the description of $L$) to decide whether $L \in P$? Are there any results on the hardness of the search version of the problem vs. the decision version?


The only result I can think of is that $P=NP$ implies the existence of such an algorithm since then an algorithm which outputs $True$ everytime works.



A polynomial-time algorithm for deciding whether a language has a polynomial time algorithm
If there is such an algorithm, then P = NP.


.


L(m) := {s : machine(m) halts within length(s) steps and sat\_instance(s) is true}


If P != NP, then "Is L(m) in P?" is equivalent to "Does machine(m) run forever?".


