Computability and Basic Complexity Theory

Draft of a Textbook in Hebrew

Oded Goldreich

The following draft for a Hebrew textbook on Computability and Basic Complexity Theory was written in 1989 (with the assistence of Dror Sneh, my TA at the time). The motivation for writing this textbook was two-fold: (1) my unsatisfaction with the conceptual attitudes that underly existing textbooks on the subject, and (2) providing the Israeli student with a textbook in their language.

To explain the first motivation, let me say that in my opinion the notions of computation and efficient computation and the results obtained about them are among the most important conceptual achievements of the 20th century. Any exposition that fails to convey this fact is highly unsatisfactory. My main aim was not to fail in this aspect.

The textbook was planned to consist of two parts. In the first part, devoted to computability, we discuss and define the notion of computation, try to strike a balance between the model-independence of most phenumena and the importance of using a clear model, and prove that not every well-defined problem can be solved (providing several important examples such as the impossibility of deciding the correctness of arbitrary computer programs). In the second part, devoted to effecient computability, we discuss and define the notion of effecient computation, define and explain the fundamental nature of the "P versus NP Question", and explore the phenumenon of NP-completeness. A brief survey of the material presented in the second part appears as Sections 2--4 in my survey.

Available below are old postscript files (in Hebrew).

A few accompanying figures are available from the sub-directory HEBREW/LN.FIG/. (Sorry, I don't know how to incorporate them in the main files.)

Note: I have no intention (let alone abilility) to revise any of the files.

Back to Oded Goldreich's homepage.

Copyright (C symbol) 1989 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.