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

The short answer is:

A problem is said to be in P, is independent of the kind of Turing Machines you use (model independent, but also has to be reasonable, details ignored).

However, it is not algorithms independent. You might come up with an EXP algorithm to solve a problem in P. That does not mean the problem is not in P.

A problem is in P means *there is an algorithm* that solves the problem in polynomial time.