P = NP consequences

Started by IvanV

IvanV

"P versus NP" problem is one of the most intriguing problems in science. There has been nearly hundred proposed solutions, trying to prove either P = NP or P =!= NP, but were all refuted since Clay Mathematic Institute announced a reward to one who would solve it.

Thinking of consequences, nothing much would happen if P =!= NP is true. But in the opposite case, how would the world look like?

ddrone

There is quite a bit of discussion of different implications of P = NP online, but one relevant consequence of interest to this forum would be an existence of polynomial algorithm for graph coloring, which would make optimal register allocation possible, leading to compilers producing faster executable programs.

Polynomial solution for satisfiability problem would be handy as well for things like program verification.

Also, JFYI it's possible to type fancy math like on this forum, which would look like this: PNP\mathrm{P} \neq \mathrm{NP} ;-)

IvanV

Ddrone, tx for the answer. But I was imagining something really world changing. Maybe we should look beyond computers to answer the above question. I wonder what would applying the discovery mean to protein synthesis and what would consequences mean for humanity at social level. New medicaments? Cancer cures? Artificial organs? And last, but not least - artificial food?

Maybe I'm dreaming too much, but I think that things should go beyond just optimization and verification of code, to be worth of spending resources to find a solution.

here are some pretty abstract answers: link.

IvanV

I've been applying the question to a new programming language I work on, and I got some firm answers. It still needs to be proof-checked, but by now I'm pretty convinced that all three combinations are possible:

  1. P > NP,
  2. P = NP,
  3. P < NP,

depending on a form of construction of a function that calculates result.

Actually it is about analyzing domain and codomain of a function. For calculating results we use domain -> codomain direction. The search for acceptance or rejecting results may be linear, converge or diverge in a count of elements in the result set, exhibiting constant, linear, polynomial, exponential or infinite time termination.

For verifying results we use codomain -> domain direction, which is the same thing as calculating results, but in the another direction. Also, termination time ranges from constant to infinite, and comparing it with actual calculating results may give all combinations, from (calculating = constant, while verifying = infinite) to (calculating = infinite, while verifying = constant).

I was hoping for universal P = NP result, so I am a bit disappointed with my conclusion. I know that a $1M reward is announced for a proof of either way, but I think that in this case it would yield no major impact on the science. I think I won't claim the reward for the bad news.

ddrone

By P>NP\mathrm P > \mathrm{NP} do you mean that there can be a program in P\mathrm P that's not in NP\mathrm{NP}? From the way these complexity classes are usually defined it follows straightforwardly that PNP\mathrm P \subseteq \mathrm{NP}, and the P=NP\mathrm P = \mathrm {NP} problem is about determining whether this inclusion is strict.

I'm nevertheless curious about how exactly do you apply complexity theory to the programming language you're working on, can you elaborate on that?

IvanV

By P > NP do you mean that there can be a program in P that's not in NP?

Sorry, my bad, I should rewrite write those three points this way:

  • time for calculating result(s) can be less than, equal or grater than time for verifying result(s) of the same function, depending on the function structure.

I'm nevertheless curious about how exactly do you apply complexity theory to the programming language you're working on, can you elaborate on that?

The conclusion follows from a fact that any function domain may be either single or multiple element set, just like its codomain. We get N:M relations between arguments and results, and more the count of elements is on either side, that side is more computationaly intensive (of course, also relative to a number of steps needed for termination). In my language, I construct all complex functions by combining other complex or simple functions. Knowing that simple functions are merely N:M correspondence between constants (or variables that hold constants at the end [and I see variables as nullary functions]), I get a clear view on computational complexity of any function, being calculated in both directions, being domain -> codomain, or codomain -> domain. I'm pretty convinced about this, it is simple like a difference between earth and sky from my point of view. To be more concrete, it is exactly like comparing calculating function results vs type checking process (basically, it is the same algorithm with a different direction of a progress). Assuming that my language is computationally complete, this conclusion extrapolates to any kind of computation.

I might return with a concrete elaboration on the language, and P vs NP time complexity intuitive concusion in a PDF, if anyone would be interested.

IvanV

How would one interpret the existence of function that can fastly calculate result versus slowly check is the result valid? Printing character bitmaps versus optical character recognition represents such a dual function.

Considering that example, in my opinion, P⊆NP is a wrong assumption, i.e. there is a NP element that is not in P and the other way around, just like there also exist elements that are in both P and NP.

Brian Jacobs

Firstly: I am definitely interested in your PP vs NPNP expository PDF.

The definition which I use, at least informally, is that a problem is in PP if there exists an algorithm which solves that problem in a number of steps which is related to the "size" of the problem instance by a polynomial function. A problem is in NPNP if there exists an algorithm which takes a solution to that problem and either verifies or disproves the correctness of that solution in polynomial time. (Where by polynomial time I mean the same as above.)

By this definition, the function of printing character bitmaps is in PP by building a lookup table from input character to output bitmap. Running through this lookup table to find the appropriate bitmap to return takes at most on the order of nn steps, where nn is the number of characters in the lookup table. If the number of characters is fixed at the definition of the function, then the runtime of this algorithm is at most on the order of O(n)O(n). Since nn is a polynomial, the problem is in PP.

The function of converting a bitmap back into a character is similar, albeit with a larger lookup table. The runtimes of these functions will therefore be fairly different; I would use the character \rightarrow bitmap function without reservation, but would probably try to find a more efficient implementation of the bitmap \rightarrow character one. Despite their differences in runtime, however, they have the same asymptotic complexity, and both reside in the complexity class PP.

Perhaps you could elaborate on how you are defining PP and NPNP?

IvanV

Yes, I think we define a problem being in P or NP in the same way: when it solves or verifies a solution in polynomial time, respectively.

The example of printing character / OCR falls down to polynomial time (linear, more precisely), indeed, but printing character is undoubtedly faster than OCR. OCR checks each lookup table element against the input bitmap, while printing checks the lookup table against only a key and then extracts an output bitmap. It is an example of the same function being faster in calculation way, rather than verifying way of running (despite of superficial intuition which says that solving has to be more difficult than verifying).

Noted example of faster solving / slower verifying gives indices that there exist a case of exponential verifying / polynomial solving. To prove this existence, we have to find a function whose domain is exponentially larger or computationally more intensive, regarding to its codomain.

As a proof, let's take a general example of function AA that finds a solution in exponential and verifies a result in polynomial time. Now let's introduce its inverted function BB, and we have a general case in which solving and verifying swapped the calculating algorithms. Hence, in such a function we have a polynomial solving / exponential verifying case, and I think that now the question is only how far our imagination goes to find a real world example, as in theory things work like a charm with abstract inverse functions, deriving that PNPP \subseteq NP has to be false.

Brian Jacobs

As a proof, let's take a general example of function AA that finds a solution in exponential and verifies a result in polynomial time. Now let's introduce its inverted function BB, and we have a general case in which solving and verifying swapped the calculating algorithms.

I'm not convinced that such functions necessarily have to exist. Take, for example, the graph isomorphism problem, which is classically understood to be in NPNP. To use the structure of this discussion, we'd say that we have a function ff which has a domain of the set of pairs of graphs, and codomain True, False. You can go from a pair of graphs to a boolean value uniquely, but cannot invert this function, since for both True and False there are multiple corresponding graph pairs.

Obviously, that there exists a single problem for which you cannot construct an inverse for the function doesn't imply that no function is reversible, but I'm having a hard time coming up with any function that has a domain and range of different size and is also reversible. Perhaps you could propose one, or at least a (possibly informal, possibly nonconstructive) proof that such functions should exist?

IvanV

Sorry for a mess in mail and on forum, something went wrong with the site when I was trying to post this…

You can go from a pair of graphs to a boolean value uniquely, but cannot invert this function, since for both True and False there are multiple corresponding graph pairs.

Of course we can go back! We just have multiple value forms that correspond either to True or False. And more value forms there are, more time complexity there is to extract them.

In my opinion, all functions should be reversible, it is their nature. I think of result, say rr simply as a counterpart of parameters aa or bb. From aa, bb, and rr, we can simply construct a table with columns aa, bb and rr. When we fill the body of the table with specific corresponding values, we get tuples as rows (with possibly repeated values across rows when a single value from one row(s) corresponds to multiple value in other row(s)). Now, we can search tuples by noting either aa, either bb, either rr, or any combination of them, and getting values from other columns, in the same row(s) as we need them. Of course, multiple results could be expected with certain queries, and that is partly a reason for a greater query run time.

Brian Jacobs

It's okay. I've certainly had worse mishaps with automated emails. :-)

I believe that I see an issue:

Let ff be a function which is computable in superpolynomial time, but verifiable in polynomial time. We define the inverse of this function, f1f^{-1} to be the function such that f1(y)={xf(x)=y}f^{-1}(y) = \{x \vert f(x) = y\}. Verification that f1=Xf^{-1} = X, for some set XX, involves computing f(x)f(x) for each xXx \in X. Computing each f(x)f(x) takes polynomial time, and the process of verification is linear in the number of elements in XX, and so verification for f1f^{-1} is computable in polynomial time.

But we need verification for f1f^{-1} to happen in superpolynomial time, otherwise f1f^{-1} cannot be outside of NPNP by definition. If f1f^{-1} is in NPNP, then our claim that f1Pf^{-1} \in P but f1NPf^{-1} \notin NP does not hold. This would mean that we do not have evidence of a function that is in NPNP but not in PP, which is central to the claim that PNPP \nsubseteq NP.

IvanV

Assumption: there are two kinds of dualities here involved, and they are diagonally related. When we make a switch from ff to f1f^{-1}, verifying for ff becomes solving for f1f^{-1}, and solving for ff becomes verifying for f1f^{-1}, because it is basically the same algorithm, but in opposite direction.

A similarity between solving and verification can be seen in a simple function f(x)=x2f(x) = x^2. We get a table:

xx or f1(y)f^{-1}(y) f(x)f(x) or yy
-2 4
-1 1
0 0
1 1
2 4

For ff, we could say:

  • Solving is happening from left to right: it is printing of all right-hand values, according to known left-hand value. Relatively, solving takes as many steps as there are rows in the table.

  • Verifying, is happening from right to left: it is finding any left-hand value paired with known right-hand side. Relatively, in the worst case, verification takes as many steps as there are rows in the table.

For f1f^{-1}, we could say the opposite:

  • Solving is happening from right to left, and it is analogous (if not the same) process to verifying ff

  • Verifying is happening from left to right, and it is analogous (if not the same) process to solving ff

The only difference between solving and verifying is that in solving we print out all the answers, while in verifying we check the least of the answers (possibly all) against expected ones.

Formally, conclusions from above could be written like:


(1) (fP)(f1NP)(f \in P) \leftrightarrow (f^{-1} \in NP)
(2) (fP)(f1NP)(f \notin P) \leftrightarrow (f^{-1} \notin NP)
(3) (fNP)(f1P)(f \in NP) \leftrightarrow (f^{-1} \in P)
(4) (fNP)(f1P)(f \notin NP) \leftrightarrow (f^{-1} \notin P)


If the above assumptions are correct, and if we say:
(5) fPf \notin P
(6) fNPf \in NP

we get the following conclusions:
(from 2 and 5) f1NPf^{-1} \notin NP
(from 3 and 6) f1Pf^{-1} \in P

with no contradiction involved.


However, maybe I made a mistake by considering solving and verifying as dual sides of the same process that switches between when we invert a function.

IvanV

If we consider each computation as a simple function step from one value to another, we can see a P vs NP problem solution simply by observing different cases of value extraction.

We define functions by their types and their specific value pairs:

(type of function ff)
f:intintf: int \rightarrow int

(value pairs of function ff)
f:12f: 1 \rightarrow 2
f:23f: 2 \rightarrow 3
f:34f: 3 \rightarrow 4
......

We can also combine functions, even recursively like in factorial example:

fact:intintfact: int \rightarrow int
fact:x{xfact(x1)if x>01otherwisefact: x \rightarrow \begin{cases} x * fact (x- 1) & \text{if}\ x > 0 \\ 1 & \text{otherwise} \end{cases}

Readers familiar to functional programming are aware of algorithmic completeness of using first or higher order functions to calculate results.

If we take each function calculation step as a discrete unit of computation, we can imagine the following situations:

  • When searching 1:N values we get N computations
  • When searching M:N values, we get N computations
  • When searching N:1 values, we get just one computation

According to the previous post, we can go backwards, if we want to check the result instead of solving it. From the three enumerated cases, it is obvious that all three combinations are possible: solving can be more complex than checking; solving can be equally complex as checking; solving can be less complex than checking.

According to the observation, I propose the following Venn diagram for P vs NP situation:

PNP

Am I missing something?