P, NP and specialised Turing Machines

Question

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.

Answer 1

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.

Answer 2

Just a trivial note to underline that the efficient simulation of a Turing machine means not only that it can simulate the computation of a Turing machine and vice versa efficiently (polynomial time slowdown); but also that its input/output must be efficiently converted from one model to the other.

A trivial example: if you find a Turing equivalent device that can solve a SAT problem in constant time, but uses as input a heap of marbles (unary), then you cannot conclude anything. The same if your device uses a binary input but it tooks an exponential number of steps to convert an instance of SAT to the input format used by it.

Answer 3

Your understanding is very good! You can also find more info in a text if your are interested, e.g. Sipser's Intro to the Theory of Computation.

There is this idea called the Church-Turing Thesis that says anything that can be computed somehow, can be computed using a Turing Machine. (It's not provable, but just an idea, or a sort of law of nature that we think is true).

I mention this because there is also the "Extended Church Turing Thesis" that says that anything that can be computed in polynomial time somehow, can be computed in polynomial time using a Turing Machine.

There's good reason to doubt this conjecture because we know of quantum computing algorithms that get a better-than-polynomial speedup over the best known classical algorithms. However, other than that, it is thought that any classical machine you can build (certainly any variant on a Turing Machine) cannot be exponentially faster than a Turing Machine. So if your "Turing-Equivalent Machine" could run an algorithm that solved an NP-Complete problem in polynomial time, then P = NP because I could convert it to a polynomial-time algorithm for the same problem on a TM.

But if you thought up some sort of a Turing-Equivalent Machine, probably one of the first things you'd do is figure out how to simulate it with a classical TM, and that would tell you if you have a polynomial-time conversion or not. And the answer would almost certainly be yes, except maybe your could be exponentially slower (but not faster -- we think, unless it's quantum, then maybe).