Next:
About
Up:
Lecture Nine(On Sep 24,
Previous:
Lecture Nine(On Sep 24,
A complete language for
Definition
14
Theorem
11
is complete for
.
Proof
.
.
Turing Machine
and a
such that
decides
in time
.
Polynomial
: read
, Decide if
accepts
. Call program for
on input
.
bighead 2008-10-29