Context of computational complexity: Difference between revisions

Revision as of 05:25, 13 February 2010

Revision as of 16:42, 11 April 2010

Line 1:

{{orphan|date=February 2010}}

{{unreferenced|date=January 2010}}

In [[computational complexity theory]] and [[analysis of algorithms]], a number of metrics are defined describing the resources, such as time or space, that a machine needs to solve a particular problem. Interpreting these metrics meaningfully requires context, and this context is frequently implicit and depends on the field and the problem under consideration. This article describes a number of important pieces of context and how they affect metrics.

Line 8 ⟶ 6:

Metrics are usually described in terms of variables that are a function of the input. For example, the statement that [[insertion sort]] requires [[Big-O notation|O]](''n''²) comparisons is meaningless without defining ''n'', which in this case is the number of elements in the input list.

Because many different contexts use the same letters for their variables, confusion can arise. For example, the complexity of [[primality test]]s and [[multiplication algorithm]]s can be measured in two different ways: one in terms of the integers being tested or multiplied, and one in terms of the number of [[binary numeral system|binary]] digits (bits) in those integers. For example, if ''n'' is the integer being tested for primality, [[trial division]] can test it in ΘΘ(n^1/2) arithmetic operations; but if ''n'' is the number of bits in the integer being tested for primality, it requires ΘΘ(2^n/2) time. In the fields of [[cryptography]] and [[computational number theory]], it is more typical to define the variable as the number of bits in the input integers.

In the field of [[computational complexity theory]], the input is usually specified as a binary string (or a string in some fixed alphabet), and the variable is usually the number of bits in this string. This measure depends on the specific encoding of the input, which must be specified. For example, if the input is an integer specified using [[unary coding]], trial division will require only ΘΘ(n^1/2) arithmetic operations; but if the same input is specified in binary (or any larger base) the complexity rises to ΘΘ(2^n/2) operations, not because the algorithm is taking any additional time, but because the number of bits in the input ''n'' has become exponentially smaller. In the other direction, ''succinct circuits'' are compact representations of a limited class of [[graph (mathematics)|graph]]s that occupy exponentially less space than ordinary representations like adjacency lists. Many graph algorithms on succinct circuits are [[EXPTIME-complete]], whereas the same problems expressed with conventional representations are only [[P-complete]], because the succinct circuit inputs have smaller encodings.

[[Output-sensitive algorithm]]s define their complexity not only in terms of their input but also their output. For example, [[Chan's algorithm]] can compute the [[convex hull]] of a set of points in O(''n'' log ''h'') time, where ''n'' is the number of points in the input and ''h'' is the number of points in the resulting convex hull, a subset of the input points. Because every input point ''might'' be in the convex hull, an analysis in terms of the input alone would yield the less precise O(''n'' log ''n'') time.

Line 18 ⟶ 16:

== Abstract machine ==

To analyze an algorithm precisely, one must assume it is being executed by a particular [[abstract machine]]. For example, on a [[random access machine]], [[binary search algorithm|binary search]] can be used to rapidly locate a particular value in a sorted list in only O(log ''n'') comparisons, where ''n'' is the number of elements in the list; on a [[Turing machine]], this is not possible, since it can only move one memory cell at a time and so requires ΩΩ(''n'') steps to even reach an arbitrary value in the list.

Moreover, different abstract machines define different ''primitive'' operations, which are operations that can be performed in constant time. Some machines, like Turing machines, only permit one bit at a time to be read or written; these are called bit operations, and the number of bit operations required to solve a problem is called its '''bit complexity'''. Bit complexity generalizes to any machine where the memory cells are of a fixed size that does not depend on the input; for this reason, algorithms that manipulate numbers much larger than the registers on ordinary PCs are typically analyzed in terms of their bit complexity. Put another way, the bit complexity is the complexity when the word size is a single bit, where word size is the size of each memory cell and register.

Another commonly-used model has words with log ''n'' bits, where ''n'' is a variable depending on the input. For example, in [[graph algorithm]]s, it is typical to assume that the vertices are numbered 1 through ''n'' and that each memory cell can hold any of these values, so that they can refer to any vertex. This is justified in problems where the input uses ΩΩ(''n'') words of storage, since on real computers, the memory cell and register size is typically selected in order to be able to index any word in memory. Operations on these words, such as copies and arithmetic operations, are assumed to operate in constant time, rather than O(log ''n'') time. The number of word operations required to solve a problem in this model is sometimes called its '''word complexity'''.

In [[computational complexity theory]], researchers intentionally define [[complexity class]]es in a way intended to make them machine-independent - that is, if a problem lies in a particular class relative to a particular "reasonable" machine, it will lie in that class relative to any "reasonable" machine. For example, as mentioned above, the time complexity of [[binary search algorithm|binary search]] depends on whether a Turing machine or a random access machine is used; but regardless of the machine choice, it lies in '''[[P (complexity)|P]]''', the class of polynomial-time algorithms. In general, '''P''' is considered a machine-independent class because any operation that can be simulated in polynomial time can be assumed to require constant time, since it can be treated as a subroutine without exceeding the polynomial-time bound.