✳flâneur — a map of the web's best reading

Computational Complexity Theory (Stanford Encyclopedia of Philosophy)

plato.stanford.edu · 31,334 words · saved by 2 readers

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 ϕ, does it have a satisfying assignment? If we were to play chess on a board of size n×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>n>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 other hand, all known methods for solving the latter two problems require a ‘brute force’ search through a large

--> Computational Complexity Theory (Stanford Encyclopedia of Philosophy) Stanford Encyclopedia of Philosophy Menu Browse Table of Contents What's New Random Entry Chronological Archives About Editorial Information About the SEP Editorial Board How to Cite the SEP Special Characters Advanced Tools Contact Support SEP Support the SEP PDFs for SEP Friends Make a Donation SEPIA for Libraries Entry Navigation Entry Contents Bibliography Academic Tools Friends PDF Preview Author and Citation Info Back to Top Computational Complexity Theory First published Mon Jul 27, 2015; substantive revision Wed

Explore this link on the map →

saved by

related reading