Table of Contents

turing-machine [cpsc/turing-machine]

References

Backlinks

polytime computable
Overview of the course
Worst case analysis
Time Hierarchy Theorem
Runtime
Reductions
Facets of Reductions
Polytime Computable
Revising the Church-Turing thesis
Computability vs. Complexity
Complexity class
Certificates and Verifiers
Amplification
TIME(t(n))