## Computational complexity theory |

**Computational complexity theory** is a branch of the

A problem is regarded as inherently difficult if its solution requires significant resources, whatever the algorithm used. The theory formalizes this intuition, by introducing mathematical

Closely related fields in theoretical computer science are

- computational problems
- machine models and complexity measures
- complexity classes
- important open problems
- intractability
- history
- see also
- references
- external links

A *instances* together with a *solution* for every instance. The input string for a computational problem is referred to as a problem instance, and should not be confused with the problem itself. In computational complexity theory, a problem refers to the abstract question to be solved. In contrast, an instance of this problem is a rather concrete utterance, which can serve as the input for a decision problem. For example, consider the problem of *instance* is a particular input to the problem, and the *solution* is the output corresponding to the given input.

To further highlight the difference between a problem and an instance, consider the following instance of the decision version of the

When considering computational problems, a problem instance is a

Even though some proofs of complexity-theoretic theorems regularly assume some concrete choice of input encoding, one tries to keep the discussion abstract enough to be independent of the choice of encoding. This can be achieved by ensuring that different representations can be transformed into each other efficiently.

*yes* or *no*, or alternately either 1 or 0. A decision problem can be viewed as a *yes*, the algorithm is said to accept the input string, otherwise it is said to reject the input.

An example of a decision problem is the following. The input is an arbitrary

A

It is tempting to think that the notion of function problems is much richer than the notion of decision problems. However, this is not really the case, since function problems can be recast as decision problems. For example, the multiplication of two integers can be expressed as the set of triples (*a*, *b*, *c*) such that the relation *a* × *b* = *c* holds. Deciding whether a given triple is a member of this set corresponds to solving the problem of multiplying two numbers.

To measure the difficulty of solving a computational problem, one may wish to see how much time the best algorithm requires to solve the problem. However, the running time may, in general, depend on the instance. In particular, larger instances will require more time to solve. Thus the time required to solve a problem (or the space required, or any measure of complexity) is calculated as a function of the size of the instance. This is usually taken to be the size of the input in bits. Complexity theory is interested in how algorithms scale with an increase in the input size. For instance, in the problem of finding whether a graph is connected, how much more time does it take to solve a problem for a graph with 2*n* vertices compared to the time taken for a graph with *n* vertices?

If the input size is *n*, the time taken can be expressed as a function of *n*. Since the time taken on different inputs of the same size can be different, the worst-case time complexity T(*n*) is defined to be the maximum time taken over all inputs of size *n*. If T(*n*) is a polynomial in *n*, then the algorithm is said to be a

Other Languages

العربية: نظرية التعقيد الحسابي

asturianu: Teoría de la complexidá computacional

বাংলা: গণনামূলক জটিলতা তত্ত্ব

български: Теория на изчислителната сложност

català: Complexitat computacional

čeština: Teorie složitosti

Deutsch: Komplexitätstheorie

eesti: Algoritmiline keerukus

Ελληνικά: Θεωρία πολυπλοκότητας

فارسی: نظریه پیچیدگی محاسباتی

galego: Complexidade computacional

한국어: 계산 복잡도 이론

hrvatski: Računska teorija složenosti

italiano: Teoria della complessità computazionale

עברית: תורת הסיבוכיות

lietuvių: Algoritmų sudėtingumas

Bahasa Melayu: Teori kekompleksan pengiraan

Mirandés: Cumplexidade cumputacional

Nederlands: Computationele complexiteitstheorie

日本語: 計算複雑性理論

norsk: Kompleksitetsteori

polski: Złożoność obliczeniowa

português: Complexidade computacional

română: Teoria complexității

русский: Вычислительная сложность

Simple English: Computational complexity theory

slovenčina: Teória zložitosti

српски / srpski: Теорија комплексности

srpskohrvatski / српскохрватски: Računska teorija složenosti

svenska: Komplexitet (beräkningsvetenskap)

Türkçe: Hesaplamalı karmaşıklık teorisi

українська: Теорія складності обчислень

Tiếng Việt: Lý thuyết độ phức tạp tính toán

中文: 計算複雜性理論