[FOM] P =? NP: A practically important breakthrough

[Kreinovich, Vladik]

>From the practical viewpoint, the P =? NP problem is almost
solved: a 2015 breakthrough

At the 56th Annual Symposium on Foundations of Computer Science
FOCS'2015, organized by the IEEE Computer Society, the Best Paper
Award was given to a paper "An average-case depth hierarchy
theorem for Boolean circuits" by Benjamin Rossman, Rocco A.
Servedio, and Li-Yang Tan (pp. 1030-1048 in the conference
proceedings). Their main result is that for a random oracle A,
with probability 1, all the classes from the polynomial hierarchy
are different -- in particular, the relativized classes NP^A and
P^A are different.

While this result is an important theoretical breakthrough, to
many researchers outside theoretical computer science, this may
seem to be a technical results of no direct interest to their
research areas. However, a deeper analysis shows that the above
result is indeed practically important: namely, it (almost)
answers the practical question behind the famous P =? NP problem.

Indeed, let us recall the practical origin of the P =? NP problem.
The corresponding class of problems started with the observation
that not all algorithms are feasible. While linear-time
algorithms, quadratic-time algorithms etc. are usually feasible,
for algorithm whose running time grows exponentially with the
input length (e.g., exhaustive search), running time exceeds
lifetime of the Universe already for reasonable-size inputs. It is
therefore important to distinguish between practically feasible
and non-feasible algorithms. There is no perfect way to make this
distinction. The best known definition is that an algorithm is
feasible if and only if its running time is bounded by a
polynomial P(n) of the length n of the input. This definition is
not perfect: e.g., an algorithm whose running time is equal to Cn,
with C = 10^100, is feasible according to this definition (it is
linear-time), but from the practical viewpoint, it is not
feasible. However, this definition is the best we have, so it is
used in computer science.

The next is a notion of a general problem. In most practical
problems, it is difficult to come up with a solution, but it is
usually much easier to check whether a given candidate is indeed a
solution. For example, the main activity in mathematics is proving
theorems. It is often very difficult to prove a result, but once a
detailed step-by-step proof is given, it is relatively easy to
check that this proof is correct -- by simply checking that every
step in this proof is correct. Similarly, the main activity of a
physicist is to find simple laws explaining all observed data.
Coming up with such laws is not easy, but once such a law (like
Ohm's law) is formulated, it is easy to check that all available
data is consistent with this law. The main activity of an engineer
is to produce a design (or a control) that satisfies the given
specifications: e.g., the design of a bridge that can withstand a
certain weight, certain winds, and whose cost is within a given
range. Once such a design is produced, we can usually easily check
(by running the corresponding computer simulation programs) that
this design indeed satisfies all the given specifications;
however, coming up with such a design is often not easy.

In general, given an input x (formulation of a theorem, data,
specifications, etc.), we need to find y (proof, law, design,
etc.) for which some easy-to-check (feasible) property C(x,y) is
satisfied. An additional requirement is that the bit length of the
solution y should also be feasible (bounded by a polynomial
L(len(x)) of the length len(x) of the input x). Indeed, a too long
proof is impossible to check, a too long physical law makes no
physical sense (the whole point is to propose a law which is much
shorter than simply listing all the data), etc. General problems
of this type are known as Non-deterministic Polynomial (NP), since
once we _guessed_ a solution y (this is what non-deterministic
means), we can check, in polynomial time, whether this guess is
indeed a solution. The class of all such problems is denoted by
NP.

For some problems from this class, there are feasible algorithms
that always produce a solution y (whenever such a solution
exists). The class of such problems is denoted by P. The question
is whether for every such problem, there is a feasible algorithm,
i.e., whether NP is equal to P. This problem is still open.

(It is worth mentioning that the above description is somewhat
simplified: while in practice, we are interested in _finding_ y,
in theoretical computer science, the problem is formulated as
being able to _check_ whether such a y exists. From the practical
viewpoint, however, the difference between the corresponding P =?
NP questions is minor: indeed, if there is a feasible algorithm
for solving every problem from NP, then we can feasible find the
corresponding solution y bit-by-bit: first, we feasibly check
whether the solution exists, then we check whether there is a
solution with first bit 0 (if not, the solution starts with bit
1), then we similarly select the second bit etc.)

If we are solving purely mathematical problems, then P and NP are
indeed good descriptions of the corresponding classes. However, in
practice, the condition C(x,y) that we need to satisfy often
involves real data -- e.g., when we want to find a physical law. A
solution to this problem also does not have to be computable "from
scratch": often, physical laws include parameters that need to be
experimentally determined; bridge designs include, e.g.,
properties of the soil that have to be experimentally determined.
In other words, when in practice, we talk about feasible
computations, what we really mean is computations that can use
real-life data in some computational steps. Such computations are
known as _computations with an oracle_ (oracle being the sequence
of real-life measurement results).

According to modern physics -- which is based on quantum mechanics
ideas -- we have deterministic (Schroedinger) equations that
determine the wave function and the corresponding probability
distribution (which are therefore computable), and a sequence of
measurement results is random with respect to the corresponding
computable probability measure (random, e.g., in the usual sense
of Algorithmic Information Theory, or in the sense of some
modification of the corresponding definitions). It is known that
all reasonable computable probability measures are equivalent to
each other -- in the sense that they can be obtained from one
another by a computable transformation. Thus, each observable
sequence can be obtained by applying a computable transformation
to a standard random sequence -- in which all bits are
independent, and each bit is equal to 0 or 1 with equal
probability (the real number 0.01... formed by these bits is then
uniformly distributed on the interval [0,1] -- this is is what
standard computer-based random number generators produce).

Thus, allowing to use measurement results in computations is
equivalent to allowing standard random sequences (random oracles).
>From this viewpoint, in a practical problem, a polynomial-time
algorithm C(x,y) is allowed to use the random oracle A -- and a
possible feasible solution to the corresponding problem is also
allowed to use this oracle. For example, from the mathematical
viewpoint, we are interested in solving systems of equations in
which the coefficients come from the input x, but in practice,
some coefficients of the corresponding equations may come from
measurements. Thus, while _purely mathematical_ problems form a
class NP, _practical_ problems correspond to the corresponding
relativized class NP^A -- and the question of whether we can
always solve such problem in polynomial time takes the relativized
form NP^A =? P^A.

The above 2015 result states, in particular, that for a random
oracle A, NP^A is different from P^A. Thus, what
Rossman-Servedio-Tan theorem says is that if we consider
_practical_ problems, then there exist practical problems for
which no feasible algorithm is possible. In other words, THIS
THEOREM PROVIDES THE ANSWER TO EXACTLY THE QUESTION THAT IS BEHIND
THE MATHEMATICAL FORMULATION OF THE P =? NP PROBLEM.

So, this result _almost_ solves the corresponding problem. Why
almost? First, sometimes, in applications, we do need to solve
purely mathematical problems -- e.g., when we have equations that
do not have any parameters that have to be experimentally
determined. Second, in the above argument, we use quantum physics
to describe measurement results, but, as is well known, quantum
physics also leads to the possibility of quantum computing, with
ability beyond the usual non-quantum computational devices that
underlie the usual notions of P, NP, and polynomial hierarchy.
Probably, the above Rossman-Servedio-Tan result can be extended to
quantum computing as well, but this still needs to be analyzed.

Comments.

1. The 2015 result goes beyond P =? NP: it also deals with non-NP
problems, e.g., problems like optimization, where there is no easy
way to check whether a guess y is a solution -- that would require
to check that a checkable condition f(y) >= f(z) holds for all z.
It also applies to problems like selecting a move in a multi-move
game, where the goal is to make sure that after this move, for
every other move of an opponent, there is a next move on our side
etc. that eventually leads to win. In all such cases, the
condition relating y and x contains quantifiers. Problems
corresponding formulas with q quantifiers form (q + 1)-st level in
the polynomial hierarchy. Rossman-Servedio-Tan result shows that
under a random oracle, all these layers are provably different.

2. Readers interested in technical details are welcome to read not
only the original FOCS paper, but also an overview of its main
result available as: Benjamin Rossman, Rocco A. Servedio, and
Li-Yang Tan, "The Polynomial Hierarchy, Random Oracles, and
Boolean Circuits", ACM SIGACT News, 2015, Vol. 46, No. 4, pp.
50-68.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20160113/fc597448/attachment-0001.html>