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.
Tag Info
Synonyms
complexity-theoryStats
created |
6 years ago |
viewed |
34 times |
editors |
1 |
Top Answerers
more »Recent Hot Answers
An efficient isomorphism between finite fieldsComputational complexity of computing simplicial homology
Groups whose word problem can be solved in constant time
Complexity for solving linear equations?
more »
Related Tags
co.combinatorics × 123
algorithms × 119
graph-theory × 107
computer-science × 79
lo.logic × 66
nt.number-theory × 65
computability-theory × 63
reference-request × 55
np × 43
linear-algebra × 29
gr.group-theory × 23
polynomials × 18
pr.probability × 16
matrices × 14
open-problem × 14
discrete-geometry × 12
soft-question × 11
formal-languages × 10
cryptography × 10
more related tags