- 20,627
- 27,770
This article deals with the complexity of calculations, and in particular the meaning of $$P\stackrel{?}{\neq}NP.$$ Before we explain what ##P## and ##NP## actually are, we have to solve a far bigger problem: What is a calculation? And how do we measure its complexity? Many people might answer, that a calculation is an algebraic expression and its complexity the number of additions, subtractions, multiplications and divisions. However, isn't a division more complex than an addition? Isn't it strange, that we did not use the words \textit{problem} or \textit{result}? And what if we decided to differentiate or integrate? It becomes clear that we need better tools and a preciser language if we want to make all these terms rigorous. The task is clear
$$
\text{ Problem } \;\longrightarrow \; \text{ Computer } \;\longrightarrow \;\text{ Result }
$$
We need an alphabet to write the problem, a computer to do the calculations, and a decision whether we achieved a result or not. Everybody who ever mistakenly wrote an endless loop knows that the last part is not trivial. Let's start with an example with true and false. This should easily fit into our scenario.
Continue reading ...
Last edited: