Computational Model and Complexity

Entries that describe formal models of computation and the reductions and query problems used to compare how hard problems are. It covers unusual computational models, logical systems that can express any computation, approximation-preserving reductions between optimization problems, and problems studied by the number of queries they need. An entry belongs here when it is mainly a tool of computability or complexity theory rather than a procedure for solving a practical task. It excludes the complexity classes themselves, which are concepts, and optimization algorithms, which have their own subcategory.