|
Theory of Computation I
by
Peter Gacs
File Type :PDF
Number of Pages :169
Description
This note explains the basic concepts of the theory
of computation. Topics include: Turing machines and other models of
computation; Church's thesis; nondeterminism; universal algorithms,
undecidability and intractability; time and space complexity; reductions of
computational problems, NP-completeness; randomized algorithms.
|
