Context of computational complexity: Difference between revisions

Revision as of 21:42, 26 July 2008

Revision as of 21:42, 26 July 2008

Line 21:

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.

[[Oracle machine]]s are machines that have a specific operation that they can perform in constant time; this operation can be arbitrarily complex and can dramatically affect the complexity of algorithms performed on the machine. For example, if one has an oracle to solve any [[NP-complete]] problem, then any problem in '''[[NP (completecomplexity)|NP]]''' can be solved in polynomial time (whereas without the oracle, no polynomial-time algorithm is known for many of these problems). Oracle machines are impractical to construct but useful in theory for determining which proof techniques will be effective.

== Metric being measured ==