Intractable

Other resources can also be considered, such as how many Parallel Processor s are needed to solve a problem in parallel. In this case, "parallelizable time" and "non-parallelizable time" are considered. The latter is important in real-time applications, and it gives a limit to how far the computation can be parallelized. Some steps must be done sequentially because they depend on the results of previous steps.

Complexity theory differs from Computability Theory , which deals with whether a problem can be solved at all, regardless of the resources required.

OVERVIEW

After the theory explaining which problems can be solved and which cannot be, it was natural to ask about the relative computational difficulty of Computable Function s. This is the subject matter of computational complexity.

A single "problem" is an entire set of related questions, where each question is a finite-length , return all of the Prime factors of that number. A particular question is called an ''instance''. For example, "give the factors of the number 15" is one instance of the ''FACTORIZE'' problem.

The time complexity of a problem is the number of steps that it takes to solve an instance of the problem as a function of the Size Of The Input (usually measured in bits), using the most efficient Algorithm . To understand this intuitively, consider the example of an instance that is ''n'' bits long that can be solved in ''n''&² steps. In this example we say the problem has a time complexity of ''n''&². Of course, the exact number of steps will depend on exactly what machine or language is being used. To avoid that problem, we generally use Big O Notation . If a problem has time complexity O(''n''&²) on one typical computer, then it will also have complexity O(''n''&²p(n)) on most other computers for some Polynomial p(n), so this notation allows us to generalize away from the details of a particular computer.

Example: Mowing grass has linear complexity because it takes double the time to mow double the area.
However, looking up something in a dictionary has only logarithmic complexity because a double sized dictionary only has to be opened one time more (e.g. exactly in the middle - then the problem is reduced to the half).

DECISION PROBLEMS

Much of complexity theory deals with decision problems. A Decision Problem is a problem where the answer is always YES/NO. For example, the problem ''IS-PRIME'' is: given an integer written in binary, return whether it is a prime number or not. A decision problem is equivalent to a ''language'', which is a set of finite-length strings. For a given decision problem, the equivalent language is the set of all strings for which the answer is YES.

Decision problems are often considered because an arbitrary problem can always be reduced to a decision problem. For example, the problem ''HAS-FACTOR'' is: given integers ''n'' and ''k'' written in binary, return whether ''n'' has any prime factors less than ''k''. If we can solve ''HAS-FACTOR'' with a certain amount of resources, then we can use that solution to solve ''FACTORIZE'' without much more resources. Just do a Binary Search on ''k'' until you find the smallest factor of ''n''. Then divide out that factor, and repeat until you find all the factors.

Complexity theory often makes a distinction between YES answers and NO answers.
For example, the set NP is defined as the set of problems where the YES instances can be checked "quickly" (i.e. in polynomial time). The set Co-NP is the set of problems where the NO instances can be checked quickly. The "Co" in the name stands for "complement". The '' Complement '' of a problem is one where all the YES and NO answers are swapped, such as ''IS-COMPOSITE'' for ''IS-PRIME''.

An important result in complexity theory is the fact that no matter how hard a problem can get (i.e. how much time and space resources it requires), there will always be even harder problems. For time complexity, this is determined by the Time Hierarchy Theorem . A similar Space Hierarchy Theorem can also be derived.

COMPUTATIONAL RESOURCES

Complexity theory analyzes the difficulty of computational problems in terms of many different Computational Resource s. The same problem can be described in terms of the necessary amounts of many different computational resources, including time, space, randomness, Alternation , and other less-intuitive measures. A Complexity Class is the set of all of the computational problems which can be solved using a certain amount of a certain computational resource.

Perhaps the most well-studied computational resources are Deterministic Time (DTIME) and ''' Deterministic Space ''' (DSPACE). These resources represent the amount of ''computation time'' and ''memory space'' needed on a deterministic computer, like the computers that actually exist. These resources are of great practical interest, and are well-studied.

Some computational problems are easier to analyze in terms of more unusual resources. For example, a Nondeterministic Turing Machine is a computational model that is allowed to branch out to check many different possibilities at once. The nondeterministic Turing machine has very little to do with how we physically want to compute algorithms, but its branching exactly captures many of the mathematical models we want to analyze, so that Nondeterministic Time is a very important resource in analyzing computational problems.

Many more unusual computational resources have been used in complexity theory. Technically, any Complexity Measure can be viewed as a computational resource, and complexity measures are very broadly defined by the Blum Complexity Axioms .

COMPLEXITY CLASSES

A Complexity Class is the set of all of the computational problems which can be solved using a certain amount of a certain computational resource.

The complexity class P is the set of decision problems that can be solved by a Deterministic Machine in Polynomial Time . This class corresponds to an intuitive idea of the problems which can be effectively solved in the worst cases.

The complexity class NP is the set of decision problems that can be solved by a Non-deterministic Machine in polynomial time. This class contains many problems that people would like to be able to solve effectively, including the Boolean Satisfiability Problem , the Hamiltonian Path Problem and the Vertex Cover Problem . All the problems in this class have the property that their solutions can be checked effectively.

Many complexity classes can be characterized in terms of the Mathematical Logic needed to express them; see Descriptive Complexity .

THE P<NOWIKI> = </NOWIKI>NP QUESTION

The question of whether P is the same set as NP is the most important open question in theoretical computer science. There is even a $1,000,000 Prize for solving it. (See Complexity Classes P And NP and ''' Oracles ''').

Questions like this motivate the concepts of ''hard'' and '' Complete ''. A set of problems ''X'' is hard for a set of problems ''Y'' if every problem in ''Y'' can be transformed easily into some problem in ''X'' with the same answer. The definition of "easily" is different in different contexts. The most important hard set is NP-hard . Set ''X'' is complete for ''Y'' if it is hard for ''Y'', and is also a subset of ''Y''. The most important complete set is NP-complete . See the articles on those two sets for more detail on the definition of "hard" and "complete".

INTRACTABILITY

Problems that are Solvable In Theory , but can't be solved in practice, are called ''intractable''. What can be solved "in practice" is open to debate, but in general only problems that have polynomial-time solutions are solvable for more than the smallest inputs. Problems that are known to be intractable include those that are EXPTIME -complete. If NP is not the same as P, then the NP-complete problems are also intractable.