Complexity Theory

Introduction

The goal of complexity theory is to provide a means for measuring needed resources for a computation. The analysis for complexity theoretic operations should not rely on particular implementations nor consider limited space or time, and all possible algorithms must be considered. Complexity theory provides a basis for algorithmic cost based on the input size, by organizing problems into complexity classes so that a revelation of appropriate solutions can exist. Within this goal, a division of computationally hard problems is distinguished from computationally easy problems via the boundary of polynomiality as per the Cobham-Edmonds thesis. Worst-case measurements are ideal because it provides an upper bound on needed resources and guarantees termination within a certain number of computational steps.

Time Complexity

The total number of steps involved in a solution to solve a problem is the function of the size of the problem, which is the measure of that problem's time complexity. The rate of growth is what is most important for measuring time complexity for a computation. For instance, a function ƒ is of order g, ƒ = O(g), such that g is an approximate growth rate. For instance, if ƒ(n) = n² + 3n - 5, then g(n) = n², hence we have O(n²). So, the theoretical approach is that the most significant term of a polynomial is used to avoid the differences in the details regarding exactly how many steps are made between various computers. In practical terms, a programmer could be concerned with the details of efficiency to some degree. However, what is of more concern to the theoretical computer scientist is computational distinguishibility between polynomial bounded problems from exponentially bounded problems. The following are some general orders that we can consider, where the red < divides what is poly-efficient and not poly-efficient:

O(c) < O(log n) < O(n) < O(n log n) < O(n^c) < O(cⁿ) < O(n!), where c is some constant.

Space Complexity

Space complexity is measured by using polynomial amounts of memory, with an infinite amount of time. The difference between space complexity and time complexity is that space can be reused. Space complexity is not affected by determinism or nondeterminism. Savitch's theorem, which is a space complexity theorem, states that by using a small amount of space, deterministic machines can simulate nondeterministic machines, where as in time complexity, time increase exponentially in this case. Savitch's theorem explicitly demonstrates that a nondeterministic TM using ƒ(n) space can be changed to a deterministic TM using only ƒ²⁽ⁿ⁾ space.

Complexity Classes

P	Deterministic Polynomial Time
P-complete	Hardest problems in P solvable on parallel computers
NP	Nondeterministic polynomial time and YES answers checkable in polynomial time
Co-NP	Nondeterministic polynomial time and NO answers checkable in polynomial time
NP-complete	Hardest problems in NP
Co-NP-complete	Hardest problems in CO-NP
NP-hard	At least as hard as NP-complete problems
NC	Solvable parallel computation efficiency
PSPACE	Polynomial memory with unlimited time
PSPACE-complete	Hardest problems in PSPACE
EXPTIME	Exponential time
EXPSPACE	Exponential memory with unlimited time
BQP	Polynomial time on a quantum computer

Links

http://www.cs.berkeley.edu/~aaronson/zoo.html
http://www.well.com/user/xanthian/link_pages/Programming/Paradigms/Computati onalComplexity.html
http://www.busygin.dp.ua/npc.html#links