P = NP consequences

"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?

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: $\mathrm{P} \neq \mathrm{NP}$ ;-)

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.

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.

By $\mathrm P > \mathrm{NP}$ do you mean that there can be a program in $\mathrm P$ that's not in $\mathrm{NP}$? From the way these complexity classes are usually defined it follows straightforwardly that $\mathrm P \subseteq \mathrm{NP}$, and the $\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?

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.

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.

Firstly: I am definitely interested in your $P$ vs $NP$ expository PDF.

The definition which I use, at least informally, is that a problem is in $P$ 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 $NP$ 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 $P$ 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 $n$ steps, where $n$ 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)$. Since $n$ is a polynomial, the problem is in $P$.

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 $P$.

Perhaps you could elaborate on how you are defining $P$ and $NP$?

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 $A$ that finds a solution in exponential and verifies a result in polynomial time. Now let's introduce its inverted function $B$, 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 $P \subseteq NP$ has to be false.

As a proof, let's take a general example of function $A$ that finds a solution in exponential and verifies a result in polynomial time. Now let's introduce its inverted function $B$, 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 $NP$. To use the structure of this discussion, we'd say that we have a function $f$ 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?

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 $r$ simply as a counterpart of parameters $a$ or $b$. From $a$, $b$, and $r$, we can simply construct a table with columns $a$, $b$ and $r$. 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 $a$, either $b$, either $r$, 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.

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

I believe that I see an issue:

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

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

Assumption: there are two kinds of dualities here involved, and they are diagonally related. When we make a switch from $f$ to $f^{-1}$, verifying for $f$ becomes solving for $f^{-1}$, and solving for $f$ becomes verifying for $f^{-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) = x^2$. We get a table:

$x$ or $f^{-1}(y)$	$f(x)$ or $y$
-2	4
-1	1
0	0
1	1
2	4

For $f$, 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 $f^{-1}$, we could say the opposite:

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

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

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) $(f \in P) \leftrightarrow (f^{-1} \in NP)$
(2) $(f \notin P) \leftrightarrow (f^{-1} \notin NP)$
(3) $(f \in NP) \leftrightarrow (f^{-1} \in P)$
(4) $(f \notin NP) \leftrightarrow (f^{-1} \notin P)$

---

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

we get the following conclusions:
(from 2 and 5) $f^{-1} \notin NP$
(from 3 and 6) $f^{-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.

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 $f$)
$f: int \rightarrow int$

(value pairs of function $f$)
$f: 1 \rightarrow 2$
$f: 2 \rightarrow 3$
$f: 3 \rightarrow 4$
$...$

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

$fact: int \rightarrow int$
$fact: 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:

Am I missing something?