Until such a machine is constructed, it seems quite possible that any one quantum algorithm can be simulated in polynomial time on a classical computer, yet access to a quantum computer whose program you can change gives you more computational power than a classical computer.

]]>If I use $M$ since $C$ is not satisfied then I cannot solve $X$ in polynomial time.

The converse: If I solve $X$ in polynomial time then $C$ will be satisfied in method $M$ may or may not be true.

The fundamental problem in proofs in theory CS seems to be of finding such a method $M$ and constraint $C$ so that the converse will also be true and thus violating the first statement. And hence $X$ cannot have polynomial time.

]]>I would like to suggest another question: can you construct a machine model of creativity? I think that is badly posed. For example, take a standard example of creativity: Kepler finding the ellipses. If your computer’s search space included ellipses in the first place, the problem would be trivial. If it did not, and it’s program did not contain suggestions like “if you’ve got too many circles in your fit, start looking for other conic sections”, then it would be impossible. And the problem is, once you know circles won’t do, there are too many other places to look. So, I would say, yes, it _is_ harder to discover a solution (the search space is too large) than to check it.

]]>—

Certainly there must be provably exponentially hard problems, no? Why is the above question relevant to the P vs NP problem? ]]>

The natural question (though pure speculation): would solving one such instance also solve the other instances? Or in other words: is this class of problems essentially one problem? Or still a whole class of loosely related problems?

]]>It seems reasonable that a Problem appears to be in P if there is much underlying structure wich could be used to design a shortcut-algorithm.

The main difficulty in proving lower bounds seems to be, that it is very hard to proof statements about all possible algorithms one could ever invent.

Instead of looking at the possible algorithms for a problem, one might look at the underlying structure of the problem.

It is a very easy problem to decide if a number is a multiple

of 10. Primality testing is in P as well, but it takes more

steps. Couldn’t one argue that the set of multiples of 10

has more underlying structure than the prime numbers, because the prime numbers look more randomly distributed within the natural numbers.

I wonder if one could find a way to order all possible graphs,

might it be possible to show that the set of graphs wich have a hamilton cycle look very randomly distributed within all graphs?

If this doesn’t work, i’m still curious if it would make sense

to try to find a way to measure the underlying mathematical

structure of a problem 🙂