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.