I have a decision problem that I have formulated as a feasibility SDP. The answer to the decision problem depends on whether the SDP is feasible or not. It is known that a SDP can be solved to arbitrary precision in time that is polynomial in the input size as well as the precision value. Now can I claim that I have a polynomial time algorithm for my decision problem?
[Math] SDP Feasibility
algorithmscomputational complexityoc.optimization-and-control
Related Solutions
This phenomenon extends beyond the traveling salesman problem, and even beyond NP, for there are even some undecidable problems with the feature that most instances can be solved very quickly.
There is an emerging subfield of complexity theory called generic-case complexity, which is concerned with decision problems in the generic case, the problem of solving most or nearly all instances of a given problem. This contrasts with the situtation in the classical complexity theory, where it is in effect the worst-case complexity that drives many complexity classifications. (And even for approximate solutions in NP-hard problems, the worst-case phenomenon is still present.)
Particularly interesting is the black-hole phenomenon, the phenomenon by which the difficulty of an infeasible or even undecidable problem is concentrated in a very tiny region, outside of which it is easy. (Here, tiny means tiny with respect to some natural measure, such as asymptotic density.) For example, many of the classical decision problems from combinatorial group theory, such as the word problem and the conjugacy problem are linear time solvable in the generic case. This phenomenon provides a negative answer to analogue of your question 1 for these problems. The fact that the problems are easily solved outside the black hole provides a negative answer to the analogue of question 2. And I think that the fact that these problems are actually undecidable as total problems suggests that this manner of solving almost all cases of a problem will not help us with P vs. NP, in your question 3.
For question 4, let me mention that an extreme version of the black-hole phenomenon is provided even by the classical halting problem. Of course, this is the most famous of undecidable problems. Nevertheless, Alexei Miasnikov and I proved that for one of the standard Turing machine models with a one-way infinite tape, there is an algorithm that solves the halting problem on a set of asymptotic measure one. That is, there is a set A of Turing machine programs, such that (1) almost every program is in A, in the sense of asymptotic density, (2) A is linear time decidable, and (3) the halting problem is linear time decidable for programs in A. This result appears in (J. D. Hamkins and A. Miasnikov, The halting problem is decidable on a set of asymptotic probability one, Notre Dame J. Formal Logic 47, 2006. http://arxiv.org/abs/math/0504351). Inside the black hole, the complement of A, of course, the problem is intractible. The proof, unfortunately, does not fully generalize to all the other implementations of Turing machines, since for other models one finds a black hole of some measure intermediate between 0 and 1, rather than measure 0.
Short answer: Yes and yes. For the first question, you could take any $EXPTIME$-complete problem. For the second you could take any $NEXPTIME$-complete problem.
Long answer:
Your first question is answered by the problem:
Given a deterministic Turing machine M, string x, and integer k in binary, does M accept x within k steps?
The output is one bit (yes or no). The above problem is $EXPTIME$-complete, hence it requires time that is exponential in the lengths of M, x, and k. It is crucial that k be written in binary. If it were written in unary (as a string of k ones) then it is solvable in polynomial time by direct simulation.
Your second question is answered by the problem:
Given a nondeterministic Turing machine N, string x, and integer k in binary, is there an accepting computation path in N(x) that has at most k steps?
Again the output is just one bit. The above problem is $NEXPTIME$-complete, and hence requires exponential time even on a nondeterministic machine. Again it is crucial that k is written in binary; if it were written in unary then the above problem is $NP$-complete, and is more commonly known as the "Bounded Halting Problem".
This can all be found in the early chapters of any text on complexity theory.
Best Answer
No, you can't. If you could, then you would, among other things, have a solution to what is known as the square root problem: given $a_1, \ldots, a_n,k$ determine whether $ \sum_{i=1}^n \sqrt{a_i} \leq k.$ This looks like a solvable problem - just compute the square roots- but is actually difficult, because its unclear to what precision the square roots need to be computed. Now observe that this is equivalent to asking whether there is a point $(z_1, \ldots, z_n)$ that makes the following SDP feasible:
$$ \sum_{i=1}^n z_i \leq k, ~~~z_i \geq 0, ~~~~\left( \matrix{ 1 & z_i \cr z_i & a_i} \right) \preceq 0$$
Finally, I suspect you would get better answers if you ask on cstheory.stackexchange.com, which is visited by many of the experts on these sorts of questions.