Content deleted Content added
No edit summary |
Succint circuits |
||
Line 7:
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<sup>1/2</sup>) arithmetic operations; but if ''n'' is the number of bits in the integer being tested for primality, it requires Θ(2<sup>n/2</sup>) 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<sup>1/2</sup>) arithmetic operations; but if the same input is specified in binary (or any larger base) the complexity rises to Θ(2<sup>n/2</sup>) 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.
| |||