I am reading the book "The Outer Limits of Reason" and came across a description that I am very confused about. I am afraid to say that this may be because I am not a native English speaker.
These are the contexts from The Outer Limits of Reason:
On p.136 it says:
After seeing some examples, let's find a nice definition. We
denotes with NP the class of all decision problems, the 2n, n! or less require
Operations to be Solved.6 A problem in NP is called an “NP problem”. There is P
the class of problems that can be solved in a polynomial set of operations, and
Polynomials grow more slowly than exponential or faculty functions, we have
P is a subset of NP. This means that every "simple" problem is an element of
the class of all "hard and simple" problems.
and on p.142:
We don't want the transformer to arbitrarily change an instance of Problem A.
an instance of problem B. We require that the instances have the same answer. in the
In other words, we will insist that the transformer accept inputs with a "yes" answer for
Problem A to inputs that answer "Yes" for problem B. If an entrance to problem A gets a
Answer “No” from the problem A decision maker, the transformer should issue an instance
that will have a "no" answer. We have another requirement: this transformer
should do its job in a polynomial set of operations, The need for it
The determination quickly becomes obvious.
Once we have shown that a particular problem cannot be solved, it is not difficult to show
that there is another problem too. The method used is to reduce one problem to another.
or a reduction.5 Suppose there are two decision problems: problem A and problem
B. Also assume that there is a way to transform a problem instance
A into an instance of problem B so that an instance of problem A has a yes
The answer is forwarded to an instance of Problem B with the same answer, for
No answers. (We do not make the requirement, as we did in the last chapter, that the
Transformation in a polynomial number of operations, We don't have any here
Interest in how long such a transformation takes, only whether it can be carried out.) We
could imagine this transformation as in Figure 6.6.
First some definitions. P was defined as the set of problems that can be solved by
a normal computer in a polynomial number of operations, We generalize. Consider
each oracle X. Define PX as 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 it can
be solved by a normal computer in at most an exponential or factorial number of
Operations. NPX is the set of X oracle problems that can be solved in at most exponential or factorial numbers of operations.
These are repeated several times, but I think it's enough. My problem is in bold parts. What does it mean "in a poly set / number of operations"? because I always thought it was "in a lot / number of polynomial operations. Please keep it simple.