p.4 Complexity theory offers its own perspective on the concept of knowledge (and distinguishes it from information). Specifically, Complexity Theory views knowledge as the result of a hard computation. Thus, whatever can be efficiently done by anyone is not considered knowledge. In particular, the result of an easy computation applied to publicly available information is not considered knowledge. In contrast, the value of a hard-to-compute function applied to publicly available information is knowledge, and if somebody provides you with such a value then it has provided you with knowledge.

p.5 Another concept related to knowledge is that of secrecy: Knowledge is something that one party has while another party does not have (and cannot feasibly obtain by itself) - thus, in some sense knowledge is a secret.

p.6 We are successful because we use the right level of abstraction. Avi Wigderson (1996)

Using the "right level of abstraction" seems to be a main characteristic of the theory of computation at large. The right level of abstraction means abstracting away second-order details, which tend to be context dependent, while using definitions that reflect the main issues... Indeed, using the right level of abstraction calls for an extensive exercising of good judgment

p.7 One major choice, taken by the theory of computation at large, is the choice of a model of computation and corresponding complexity measures and classes. The choice, which is currently taken for granted, was to use a simple model that avoids both the extreme of being too realistic (and thus too detailed) as well as the extreme of being too abstract (and vague).

p.7 One aspect that makes Complexity Theory unique is its perspective on the most basic question of the theory of computation, that is, the way it studies the question of what can be efficiently computed. The perspective of Complexity Theory is general in nature.

p.13 Complexity Theory evolves around the notion of efficient computation.

p.19 A search problem consists of a specification of a set of valid solutions (possibly an empty one) for each possible instance... For example, consider the problem in which one is given a system of equations and is asked to find a valid solution. Needless to say, much of computer science is concerned with solving various search problems

p.20 We are all familiar with computers and with the ability of computer programs to manipulate data. This familiarity seems to be rooted in the positive side of computing; that is, we have some experience regarding some things that computers can do. In contrast, Complexity Theory is focused at what computers cannot do, or rather with drawing the line between what can be done and what cannot be done. Drawing such a line requires a precise formulation of all possible computational processes; that is, we should have a clear model of all possible computational processes (rather than some familiarity with some computational processes.

p.21 A computation is a process that modifies an environment via repeated applications of a predetermined rule... the notion of a computation can be used to model the "mechanical" aspects of the natural reality, that is, the rules that determine the evolution of reality... In this case, the starting point of the study is the actual evolution process that takes place in the natural reality, and the goal of the study is finding the (computation) rule that underlies this natural process. In a sense, the goal of science at large can be phrased as finding (simple) rules that govern various aspects of reality (or rather one's abstraction of these aspects of reality).

p.47 Much of computer science is concerned with solving various search problems.

p.57 Intuition and concepts constitute... the elements of all our knowledge, so that neither concepts without an intuition in some way corresponding to them, nor intuition without concepts, can yield knowledge. Immanuel Kant (1724-1804)

p.88 In the context of search problems, a promise problem is a relaxation in which one is only required to find solutions to instances in a predetermined set, called the promise.

p.284 What matters is how the world looks to us and to various computationally bounded devices.

p.416 In light of the apparent infeasibility of solving numerous useful computational problems, it is natural to ask whether these problems can be relaxed such that the relaxation is both useful and allows for feasible solving procedures.

p.417 Two major questions regarding approximation are (1) what constitutes a "good" approximation, and (2) whether it can be found more easily than finding an exact solution.

p.482 It is possible to build a cabin with no foundation, but not a lasting building. Eng. Isidor Goldreich (1906-95)