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.
It means that the number of operations required can be described by a polynomial. For example, to look at every element of a $1\times r$ vector requires $r$ operations (look at each element in turn). This is polynomial in $r: P(r)=r$ is a polynomial and will tell you exactly how many operations are needed for any $1\times r$ vector.
An $m\times r$ matrix with $m\lt r$ would require no more than $P(r)=r^2$ operations to look at each element, so this is also polynomial.
Things change when you need an exponential number of operations to evaluate something. To enumerate the power set of a given set $X$ you need $2^{|X|}$ operations, where $|X|=\mathop{\mathrm {card}} X$ is the cardinality of the set and this is strictly larger than any polynomial operation.
Things that can be done in polynomial time can be viewed as being computationally feasible (although some of them may, at the moment, still be larger than we have reasonable computing power to achieve). Things in non-polynomial times may only be computationally feasible if we have a way to do it that isn't brute force.