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.

- Cover page.
- Table of Contents.
- Introduction and Background.
- Part 1: Computability.
- Lecture 1: The notion of Computation.
- Lecture 2: The (simple) model of Turing machines.
- Lecture 3: Programming techniques for Turing machines.
- Lecture 4: Variants on the Turing machine model.
- Lecture 5: Other Models of Computation.
- Lecture 6: Church's Thesis and Recursive Functions.
- Lecture 7: Turing machines as language accepting devices and related topics.
- Lecture 8: Universal machines (encoding, simulation, and Kolmogorov Complexity).
- Lecture 9: Incomputable functions (a counting argument, the Halting Problem, and Rice's Theorem).
- Lecture 10: Reductions.
- Lecture 11: Undecidability of Combinatorial Problems.
- Concluding Comments for Part 1.

- Part 2: Efficient Computability (i.e., Basic Complexity).
- Lecture 12: Efficient Computations.
- Lecture 13: Finding solutions versus verifying their correctness (P vs NP).
- Lecture 14: P versus NP and NP-completeness.
- Lecture 15: NP-completeness of furmula satisfiability (SAT and 3SAT).
- Lecture 16: NP-completeness of Combinatorial Problems (VS, SC and 3XC).
- Lecture 17: Facing NP-complete problems (restrictions and approximation).
- Concluding Comments for Part 2.
- Lecture 18: Other complexity classes (BPP, RP, within NP-P, and beyong NP).

- Solutions of Selected Exercises of Part 1.
- Solutions of Selected Exercises of Part 2.

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.