Meta & resources
Probability, statistics and data analysis
Machine Learning: concepts & procedures
Machine Learning: fundamental algorithms
Machine Learning: model assessment
Artificial neural networks
Natural language processing
The computer science appendix
The mathematics appendix
Computational models and algorithmic complexity
The Turing Machine
The Turing machine is an idealisation of a computational device, effectively a mathematical representation. It is composed by an infinite tape where symbols are sequentially written, a scanning element that reads what is in the current location of the tape, and a set of instructions (rules) to be followed. The rules specify what to do when a certain symbol is encountered: the machine can overwrite it with another one, erase it or do nothing. It is conceived as a model for computation as it can perform any algorithm.
A universal Turing machine is capable of simulating any Turing machine on any possible input.
Deterministic and non-deterministic cases
The Turing machine is deterministic when the rule applied to the same situation is always the same. It is non-deterministic when the rule for the same situation is not unique.
Complexity classes of algorithms
​
P class
The P complexity class is the class of all computational problems that are efficiently solvable, that is, solvable in polynomial time by a deterministic Turing Machine. It's not necessarily straightforward to prove that a problem can be solved deterministically in polynomial time, and research in the field is still very much active: the Agrawal paper proved (in 2004) that detecting if a number is prime is P.
NP, NP-hard and NP-complete classes
The NP (non-deterministic polynomial) class is that of all computational problems for which a solution can be found in polynomial time by a non-deterministic Turing machine. An equivalent definition is that NP problems are those verifiable efficiently, that is in polynomial time with deterministic computation. It can be shown that the two definitions are equivalent. NP-hard problems are those which are at least as hard as the hardest problems in the NP class. The NP-complete problems are those problems which are both NP and NP-hard.
P versus NP
The P problems are those "efficiently solvable", the NP ones are those "efficiently verifiable" (given the solution, it can be verified); efficiently here means in polynomial time and with deterministic computation. The P versus NP is an open question in computer science: can all problems which can be efficiently verified also be efficiently solved? Head to the Fortnow paper for a very readable explanation and review of the efforts in the area.
​
References
- 1.
- 2.
- 3.
- 4.