Introduction to Complexity Theory
(Lecture Notes - Corrections and Additions)
Oded Goldreich
Following is a list of major corrections and additions
to the lecture notes.
For more details see
PSfile.
Currently the list contains a single item.
- When defining the class RL Lecture 7 (cf., Sec. 7.6),
one needs to explicitly restrict the machine's running time
(to be polynomial). Failing to do so (i.e., allowing exponential
running time) yields a class that equals NL.
- The class PP as defined in Lecture 7 (cf., Def. 7.6),
is computationally equivalent to the class #P
as defined in Lecture 10 (cf., Def. 10.4)
in the sense that each class is Cook-reducible to the other.
Recall that the class PP was referred to in Lecture 7
as a probabilistic complexity class that allows ``useless''
algorithms (i.e., the difference in their behavior,
on YES and NO-instances, may be negligible).
What we forgot to mention is that PP is strongly related
(as stated above) to the counting (complexity) class #P.
Back to Oded Goldreich's homepage
or to main page of these notes.
Copyright (C symbol) 1999 by Oded Goldreich.
Permission to make digital or
hard copies of part or all of this work for personal or
classroom use is granted without fee provided that copies
are not made or distributed for profit or commercial
advantage and that new copies bear this notice and the full
citation on the first page. Abstracting with credit is permitted.
This work may be published or be a basis for publication in the future.
Copyright may be transferred without further notice and this
version may no longer be accessible.