Access to the full content is only available to members of institutions that have purchased access. If you belong to such an institution, please log in or find out more about how to order.

### Contents

• content locked
1
• content locked
2
• content locked
3
• content locked
4
• content locked

# Complexity, computational

DOI
10.4324/9780415249126-Y007-1
DOI: 10.4324/9780415249126-Y007-1
Version: v1,  Published online: 1998
Retrieved November 30, 2022, from https://www.rep.routledge.com/articles/thematic/complexity-computational/v-1

## Article Summary

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.