Complexity, computational

The theory of computational complexity is concerned with estimating the resources a computer needs to solve a given problem. The basic resources are time (number of steps executed) and space (amount of memory used). There are problems in logic, algebra and combinatorial games that are solvable in principle by a computer, but computationally intractable because the resources required by relatively small instances are practically infeasible.

The theory of $\mathcal{NP}$ -completeness concerns a common type of problem in which a solution is easy to check but may be hard to find. Such problems belong to the class $\mathcal{NP}$ ; the hardest ones of this type are the $\mathcal{NP}$ -complete problems. The problem of determining whether a formula of propositional logic is satisfiable or not is $\mathcal{NP}$ -complete. The class of problems with feasible solutions is commonly identified with the class $\mathcal{P}$ of problems solvable in polynomial time. Assuming this identification, the conjecture that some $\mathcal{NP}$ problems require infeasibly long times for their solution is equivalent to the conjecture that $\mathcal{P}\ne \mathcal{NP}$ . Although the conjecture remains open, it is widely believed that $\mathcal{NP}$ -complete problems are computationally intractable.