Computational Complexity Theory

[Revised entry by Walter Dean on July 20, 2016. Changes to: Main text, Bibliography] Computational complexity theory is a subfield of theoretical computer science one of whose primary goals is to
Philosophy News image
[Revised entry by Walter Dean on July 20, 2016. Changes to: Main text, Bibliography] Computational complexity theory is a subfield of theoretical computer science one of whose primary goals is to classify and compare the practical difficulty of solving problems about finite combinatorial objects - e.g. given two natural numbers (n) and (m), are they relatively prime? Given a propositional formula (phi), does it have a satisfying assignment? If we were to play chess on a board of size (n times n), does white have a winning strategy from a given initial position? These problems are equally difficult from the standpoint of classical computability theory in the sense that they are all effectively decidable. Yet they still appear to differ significantly in practical difficulty. For having been supplied with a pair of numbers (m gt n gt 0), it is possible to determine their relative primality by a method (Euclid's algorithm) which requires a number of steps proportional to (log(n)). On the. . .

Continue reading . . .

News source: Stanford Encyclopedia of Philosophy

blog comments powered by Disqus