0
$\begingroup$

I am currently reading the book ''The Outer Limits of Reason'' and encountered a description about which I am very confused. I am afraid to say, this may be due to the fact that I am not a native English speaker. these are the contexts from ''The Outer Limits of Reason'':

On pp.136, it says:

Now that we’ve seen a few examples, let’s come up with a nice definition. We will denote by NP the class of all decision problems that require 2n, n!, or fewer operations to solve.6 A problem in NP will be called an “NP problem.” Since P is the class of problems that can be solved in a polynomial amount of operations, and polynomials grow more slowly than exponential or factorial functions, we have that P is a subset of NP. What this means is that every “easy” problem is an element of the class of all “hard and easy” problems.

and on pp.142:

We don’t want the transformer to arbitrarily change an instance of Problem A into an instance of Problem B. We require that the instances have the same answer. In other words, we will insist that the transformer take inputs with a “Yes” answer for Problem A to inputs that answer “Yes” for Problem B. If an input to Problem A gets a “No” answer from the Problem A decider, the transformer should output an instance that will have a “No” answer. We make one further requirement: this transformer should perform its task in a polynomial amount of operations. The need for this stipulation will quickly become apparent.

on pp.169:

Once we have shown that a particular problem is unsolvable, it is not hard to show that another problem is as well. The method used is reducing one problem to another, or a reduction.5 Suppose there are two decision problems: Problem A and Problem B. Furthermore, assume that there is a method of transforming an instance of Problem A into an instance of Problem B such that an instance of Problem A that has a Yes answer will go to an instance of Problem B with the same answer, and similarly for No answers. (We do not impose the requirement as we did in the last chapter that the transformation be performed in a polynomial number of operations. Here we have no interest in how long such a transformation takes, just whether it can be done.) We might envision this transformation as in figure 6.6.

on pp.179:

First some definitions. P was defined as the set of problems that can be solved by a regular computer in a polynomial number of operations. Let us generalize. Consider any oracle X. Define PX to be the set of X-oracle problems that can be solved in a polynomial number of operations. NP was defined as the set of all problems that can be solved by a regular computer in at most an exponential or factorial number of operations. Let NPX denote the set of X oracle problems that can be solved in at most exponential or factorial number of operations.

These are repeated several other times but I think it is sufficient. My problem is with bolded parts. What does it mean "in a polynomial amount/number of operations"? because I always thought it is "in a amount/number of polynomial operations. Please keep it simple.

$\endgroup$
  • 1
    $\begingroup$ That book is completely wrong in how it defines NP ("We will denote by NP the class of all decision problems that require 2^n, n!, or fewer operations to solve."). If you want to learn about complexity theory, this is not a good book to read. $\endgroup$ – Tom van der Zanden Feb 27 at 9:35