argues that a problem can be solved with a feasible amount of resources if and only if it admits a polynomial-time algorithm.

Machine models and complexity measures

Turing machine

A Turing machine is a mathematical model of a general computing machine. It is a theoretical device that manipulates symbols contained on a strip of tape. Turing machines are not intended as a practical computing technology, but rather as a general model of a computing machine--anything from an advanced supercomputer to a mathematician with

1.Previous
3.Next