No, we don't. Show me a program that can solve the Hamiltonian path problem in polynomial time. Keep in mind that I do not mean that it can solve particular instances of the Hamiltonian path problem in polynomial time, but that it can solve all instances of the Hamiltonian path problem in polynomial time.

I guess I'm getting a bit repetitive here. Can you please answer the follow question -- what if I did produce you such an algorithm, but wouldnt tell you how it worked? Again, for mental exercise sake, lets assume, I did it. I read your question and I went away and had a eureka moment and somehow arrived at a way to find hamiltonian paths in constant time. Now, there is a million dollar prize for this discovery, so obviously, I wouldnt post it here on reddit. So maybe I build a Web server and post a link. What happens then? you start sending me graph tuples and i keep producing correct hamiltonian paths. sounds feasible? Now, instead of being incredibly smart, imagine I'm incredibly lucky. My Web server program is really nothing but a random number generator and I'm just lucky enough to consistently produce correct answers. What would that mean? Did I discover the Hamiltonian path solution or no? Do i get the 1 million prize? If not, why not? nowhere does it say that I must explain myself. I simply communicate to people that setting such and such seed values for random number generators in any language gets you this particular magic function. Not very scientific, I agree, but surely possible, right? And if it's possible, than its possible to solve NP problems in polynomial time. Can such Web server be built in our world? Why not? Does it have a non-zero chance of succeeding? Sure it does. So we have a non-zero probability of a very deterministic, concrete turing machine that walks and talks just like someone actually found a way to solve complicated problems quickly. Again, extrapolating to non-determinism, if a non-deterministic TM can do this by expressing itself as a lot of deterministic TMs, then we may get lucky enough to happen to build one in our own Java code. I'm not sure how that doesn't make sense.