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.
- 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
NPproblems can be converted to in polynomial time
Are the complexity classes (
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
Or must the
NP-complete problem be solvable on all possible Turing Machines in polynomial time to be considered in
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.