P, NP and specialised Turing Machines

Problem Detail: 

I'm sort of new, but very interested to the field of computing and complexity theory, and I want to clarify my understanding about how to class problems, and how strongly the problems relate to the machine being used to solve them.

My Understanding

• Standard Turing Machine - a Turing Machine which has a finite alphabet, finite number of states and a single right-infinite tape
• Turing-Equivalent Machine - a Turing Machine which, can emulate, and be emulated by, a Standard Turing Machine (quite often with some trade-off between space and time achieved by the emulation)
• P - the class of problems which can be solved in polynomial time using a Standard Turing Machine (defined above)
• NP - the class of problems which can be verified in polynomial time using a Standard Turing Machine
• NP-complete - the hardest problems which are still in NP, which all NP problems can be converted to in polynomial time

My Question

Are the complexity classes (P, NP, NP-complete, etc) related to the algorithm, or the algorithm and the machine?

Said in another way, if you could create a Turing Equivalent Machine (that can solve all the problems that a Standard TM can, but in a different amount of time/space) and this new machine could solve an NP-complete problem in time which grows as a polynomial with respect to the input, would that imply P=NP?

Or must the NP-complete problem be solvable on all possible Turing Machines in polynomial time to be considered in P?

Or do I mis-understand something fundamental above?

I have had a look (maybe not with the correct search terms, I don't know all the jargon quite well) but it seems most lectures/notes etc. focus on standard machines but say that custom machines often have some time/space speed up at the expense of space/time, without saying how that bears on complexity classes. I'm not really familiar enough with the jargon in this field yet to find papers which explain this.

Asked By : Bingo

Answered By : Kaveh

Algorithms and machines are not defined in your question and I don't think they are needed to ask what you want to ask.

Complexity classes are defined using Turing machines. That is their definition. If you want to prove anything you have to use these definitions. Anything about any other model is unrelated unless you prove some correspondence between that model and Turing machines.

Let me add that there is a hypothesis that says that "efficient" "computation" in any "reasonable" "machine" will capture the same number theoretic functions. However it is not a provable statement unless one defines the quoted terms. We can prove it for many machines but not all machines. Being Turing machine equivalent is not sufficient, we want them to be Strongly so, i.e. we should be able to simulate those machines with Turing machines and vice versa efficiently. The nice thing about $\mathsf{P}$ and $\mathsf{NP}$ is that they are very robust classes, i.e. small and big differences in machine models does not change the class. However it is true all the time. For example, I can define a simple new model of computation where I have an basic operation that in constant time solves a problem that is unsolvable in $\mathsf{P}$. Then it is obvious that this model will not be strongly equivalent to Turing machines.

The example above was an artificial one. However right now we have a model of computation that seems closer to efficient computation in practice than polynomial-time Turing machines: bounded-error probabilistic/randomized Turing machines, efficient algorithms in that model are referred to as $\mathsf{BPP}$.

Many experts believe that $\mathsf{BPP}=\mathsf{P}$ but we are far from proving it.

We have another model of computation which some experts expect to become practicable in future: quantum Turing machines, efficient algorithms in that model are referred to as $\mathsf{BQP}$. We don't know if it is different from $\mathsf{P}$ but some experts conjecture that it is different and more powerful than $\mathsf{P}$.

---

In short, if you want to prove a complexity theory result about $\mathsf{P}$ and $\mathsf{NP}$, you have to use either the original definitions using Turing machines, or first prove a correspondence between them and the classes you are using based on some other model of computation. As I mentioned above it is quite easy to create machine models where polynomial "time" in them can solve an $\mathsf{NP}$ (or even arbitrarily more difficult) problem: just add a basic operation to your machine model that solves that problem and let the "time" that operation takes to be one unit of time.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/9585