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.
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?".
For any NP-complete problem, search and decision are polynomially related to each other.
If we can find solutions in polynomial time then surely we can decide if a solution exists in polynomial time.
On the other hand, using self reducibility of SAT, we can show that the search problem can be solved in polynomial time using an oracle to the decision version of SAT. Here's the technique:
Suppose I am given formula F, a SAT instance on n variables, and an oracle to decide satisfiability. To solve the search problem, we show how to extend any particular partial solution by fixing a value for one more variable. Then we just start with the empty assignment and repeat this process n times.
Given F, first use Oracle to decide if F has a solution, and if it doesn't, then report Fail. Assuming that it does, we will now find a solution. Take the first variable of F, call it X_1 (any arbitrary variable will do), and plug in True for it, simplifying F accordingly. Then take this resulting formula and give it to the SAT oracle. If by hypothesizing that X_1 = True, we have now made it so that there is no solution to F, then we know that any solution will have X_1 = False. If the oracle said that there are still solutions when X_1 = True, then we retain this partial assignment and proceed. Whatever value we decided on for X_1, we plug that into F and simplify, then repeat for X_2 ... X_n. At the end we must have found a full solution.
This property is called self-reducibility of SAT -- the point is that SAT on instances of length n can be solved in polynomial time with oracle access to SAT on instances of length n-1. Clearly any other NP-complete problem has a similar self-reduction - for instance with HAM CYCLE, I could take a vertex with more than 2 edges, and then make smaller graphs by deleting one of its edges. Polynomially many graphs result this way, and each is smaller then the initial graph. If one of them has a HAM CYCLE, I can just focus on that smaller graph and start deleting edges from it... eventually, I will be left with one massive Hamiltonian cycle. If none of them has a HAM CYCLE, then I know the original graph didn't have one either.
Additionally, many NP problems that are not NP-complete will have search to decision reductions. For instance, Graph Isomorphism. Along slightly different lines, problems like Discrete Logarithm have what is called Ransom Self Reducibility -- if you have an oracle that solves a large fraction of smaller instances of a problem successfully, then you can solve the problem on a larger input size. This kind of property allows you to reduce worst case to average case, and so a way to try to establish Average Case hardness of a problem, which is important for Cryptography.
Not all NP problems are known to be self-reducible though. Although many common ones are, the result in this paper rules out any simple proof for every single problem in NP.
Your question is also tangentially related to the Dichotomy Conjecture for CSPs. The problem can be posed as follows. Given any particular CSP language, determining if a particular CSP in that language is satisfiable is an NP problem. For some CSP languages, the corresponding problem is NP-complete, for instance 3SAT, while for others such as XORSAT, the problem is known to be in P. Is it true that, for every CSP language, the corresponding problem will be solvable in polynomial time OR NP-complete? Given a description of a particular CSP language, can we determine in polynomial time whether the corresponding problem is solvable in Polynomial Time or NP-complete? There has been much work and a resurgence of interest in this problem in recent years, and it seems that top researchers are getting close to resolving it in the affirmative.
Acutally if there is such an algorithm, then false, because Rice's theorem states that every nontrivial property of the RE languages is undecidable.
