This is a branch that includes: computational complexity theory; complexity classes, NP-completeness and other completeness concepts; oracle analogues of complexity classes; complexity-theoretic computational models; regular languages; context-free languages; Komolgorov Complexity and so on.

computational complexity theory; complexity classes, such as P, NP, PSPACE, and so on; resource-limited computation; NP-completeness and other completeness concepts; oracle analogues of complexity classes; complexity-theoretic computational models such as automata, circuits; regular languages; context-free languages; applications of complexity theory to finite model theory, logic and discrete mathematics.

For those who want to ask about Kolmogorov Complexity, it is recommended that you also look for tag "information theory". Usually this tag also relates with combinatorics and logic.

Please distinguish this tag from those algorithm-specific problems that are asked on Stack Overflow, Computer Science or Theoretical Computer Science, the major concern of this category of questions should be more on the design-side instead of the implementation side.

history | excerpt history