The most interesting thing is if P=NP. If that's the case, that means that there is an algorithm that can solve any NP problem in polynomial time. This means that things like crypto would be able to be cracked in polynomial time which presents a huge problem for security.

We basically operate under the assumption that P!=NP currently. Validation that this is true doesn't really change much. I can't speak to how this may help a academic researcher in CompSci, but it probably doesn't change much for most programmers.

I think it's even less useful, even if P = NP it is possible that no one finds an algorithm. Creating a (useful) algorithm is independent of proving the theorem. Also interesting is that someone could create an algorithm that solves NP complete in polynomial time without proving P=NP. They would be unable to prove the algorithm correct though.

>> even if P = NP it is possible that no one finds an algorithm.

If someone could prove P=NP but no one could find an algorithm. That would be incredibly funny in some sense. Like a huge joke played on us by the universe.

Alternately, a polynomial time algorithm is specified and the exponent is, say, 2500. Mathematically huge, practically useless.

Actually, we already know an algorithm that solves an NP complete problem in polynomial time iff P = NP. We can just enumerate all programs and ask them to generate witnesses. As we can decide whether a witness is valid and there is a program that always outputs a valid witness if P=NP, we can find that program within finite steps and the algorithm is correct.

Correct me if I'm wrong, but enumerating all programs doesn't seem polytime

Formally, we run all possible programs in parallel: the 1st program runs for 1 step; the 1st and 2nd programs run for 1 additional step; programs 1-3 run for 1 additional step; ... After program stops, we check if its output is our witness. If there is program number K running in time f(n), then our program runs in time O(K * f^2(n) * [simulation time] * [check time]), which is polynomial if f is polynomial.

There is Universal Search algorithm. If P=NP, it finds a solution for solvable 3-SAT in polynomial time. (still not solving 3-SAT itself in case we will not be able to determine running time, but in cryptography AFAIK we usually need solutions for known-solvable instances)

This is absolutely correct. Proving P=NP doesn't magically create the algorithm, it just proves that there is one.

However, the reason why I chose to single out crypto specifically is because it has the most to lose if that algorithm exists. Our current methods of encryption become unsafe regardless of whether the algorithm is known or not. I don't think you can claim that your encryption is secure if there is an algorithm that can crack it in polynomial time, regardless of whether the algorithm is known or not.

> Proving P=NP doesn't magically create the algorithm, it just proves that there is one.

This is 100% true for all practical purposes. But there is an explicit algorithm for NP-complete problems that runs in polynomial time iff P=NP. The Wikipedia page has it written down. https://en.m.wikipedia.org/wiki/P_versus_NP_problem

It is my understanding that P = NP might have serious implications for quantum physics (ie, quantum physics suggests that P shouldn't be equal to NP).

Nah. That "result" circulated a few years ago in the Internet, but it was mostly a mix of hand waving and hidden assumptions. It's not a mainstream result, and I doubt that it will be confirmed someday.

It's interesting because it mix two interesting topics, that are well known in the popular science forums, but are very technical and most people don't want to read all technical the details of both.

Relevant xkcd: https://xkcd.com/1240/

On your second point, a construction which transforms NP-complete problems into P problems in polynomial time necessarily implies P = NP, by construction. If the algorithm isn't correct, then it's a heuristic, not an algorithm, and we have piles of heuristics for working with NP-complete problems already.

I'm pretty far out of my area of expertise, so I'll take your word for it. Could an an algorithm be correct, but not proven correct, or is it defined as a heuristic at that point?

Pretty much everything programmers do is create unproven algorithms. Hopefully at least some of them are correct. A heuristic is a problem-solving approach that has a chance of failure. So say you need a pretty fast dictionary, and you can take a relaxed attitude to correctness. You can take a hash of the words of your dictionary, and then as you are filtering some dataset, you can always say in a short time whether a value is definitely not in your dictionary, but your positive solutions have a percent chance of being incorrect (e.g. a hash collision). The idea is generally to make a problem tractable that would otherwise be computationally difficult or impossible. I'm not sure if that quite answers your question.

An algorithm could certainly be correct (in the sense of always giving the correct result) without being proven to do so (or even without any such proof existing, in some particular formal system). You are not wrong about that.

Godel's incompleteness theorem would seem to imply that is possible unless I'm misinterpreting it. I have a rather elementary understanding.

The Collatz conjecture ( https://xkcd.com/710/ ) may well be an example here.

If P=NP, then finding an algorithm is, by certain definition, exactly as easy as proving an algorithm correct! This is, after all, the gist of what P vs NP means. And this is why it's such a huge deal - the problem is almost self-referential in nature.

> This is, after all, the gist of what P vs NP means. And this is why it's such a huge deal - the problem is almost self-referential in nature.

Could you back that up with some citations? This doesn't ring true. But my pure CS has withered a bit...

For example, algorithm that just copies it's input to output, unless input is proof of inconsistency of arithmetic, is correct algorithm to calculate function f(x) = x - yet it's unprovable in PA that it's correct.

This is correct. And, in fact, P=NP.

However, while P=NP, the algorithm (oracle) resides on the other side of the event horizon. This is called the MAD paradox.

https://nerdynotmad.com/p-equals-np/

The submitted proof will be found to be incorrect.

I haven't the foggiest idea what that "proof" is supposed to mean, I can't follow any step in it. What is MAD in this context?

Would it present a problem for cryptography though? Quadratic algorithms are seen as already slow, cubic algorithms as unbearable garbage you best try to avoid if your data size is not tiny. And this completely ignores constant factors that can play a big role. Homomorphic encryption for instance fails to be usable just on a huge constant factor.

Yes, it would. The adversary in cryptography is assumed to be worst-case evil; it'll do whatever it can to break your algorithm, as long as it's performing a polynomial amount of computation. Remember, you're not just fighting your friendly neighborhood hacker, but possibly entire nation-states.

You can easily have crypto that can't be broken with all the resources and time in the observable universe even if it's "just" polynomial with a sufficiently high coefficient.

Yes, but it becomes significantly more expensive. It might work but it is a huge difference in cost tradeoffs.

Beyond crypto, problems like the traveling salesman would also be solvable in polynomial time.

Well... The traveling salesman decision problem, not the general case.

The problem of finding the optimum path is not in NP, if I give you a candidate solution you can't easily check if it's the global optimum.

What is in NP is the decision problem, finding a path that is better than a given bound. If I hand you a candidate solution, you just have to compare the sum of the distances to the bound to check it.

If you can solve the decision TSP in polytime you can solve the optimization case in polytime.

How?

edit: The wikipedia mentions that the TSP problem is NP-hard and explicitly says that the decision version of this problem is NP-complete. My assumption is that if the optimization version was proven to be NP-hard there would be no need to explicitly mention the decision version.

I can think of a way to use the decision version to find a solution to the optimization version but i feel like it must be flawed:

First we do a binary search on `L` (the length of the tour- input to the decision version) so we can find the optimal L within a factor of epsilon (maybe this epsilon is the flaw? But I don't think that is the case.) Now we pick an edge and increase its weight to infinity. Now we do the binary search again on the new graph. If the value of the optimal solution has changed it means that the edge must be in the optimal optimization solution. By doing the same process on all the edges we can find the optimal solution.

As I said there must be a flaw in the above algorithm but I can't find it.

First, use binary search to find answer. Then, remove edges one-by-one if removing this edge will not destroy all remaining path with shortest length, until your graph is reduced to a single cycle.

Thanks for the answer, I have edited my post and I have basically the same solution. (Only instead of removing the edges I increase their weight to infinity because I think the TSP problem is defined only on complete graphs) But as I have mentioned in my comment I feel like this solution is flawed.

You can without loss of generality assume that the weights are integers (if they are rational, you can multiply all weights so that they become integral).

Hence, you can use bisection to compute the actual optimum, not involving epsilon at all.

Epsilon isn't a problem, as TSP is NP-complete even for integer weights. Your solution needs some modification for case where we have multiple optimal cycles (as you will find edges that are included in at least one cycle).

I don't think there is anything wrong with optimization been reducible to decision - it's quite common method both in theory and in practice.

I didn't say there is anything wrong with reducing the optimization to decision in general. But I feel this specific application to the TSP problem may be flawed. (for the reasons i mentioned before. i.e wikipedia being very specific about the decision version) For another resource see: https://www.ibm.com/developerworks/community/blogs/jfp/entry...

note: I am not implying that the above source is reputable. But it does hint that the solution to this problem probably is not this trivial.

Decision version of TSP is NP-complete. Optimization version is Cook-reducible to decision version of TSP. And it problem is Cook-reducible to P-problem, then the problem is itself in P. (note that it's not true if you replace P with NP, for example)

Do you have a reference to a reputable source that proves the optimization version is cook-reducable to decision version?

I don't. (it's always hard to find reference for easy problems)

One minor foible. Don't select edges that are part of the minimum path, instead remove edges that are not part of the minimum path until only the minimum path remains. This strategy works even on graphs with multiple minimum paths.

I don't get why having multiple optimal paths would falsify my algorithm. Can you provide an explicit counter-example?

Here is why I think the algorithm is correct:

At each step the edge that we are considering is either contained in all the optimal solutions or only some of them. If the edge is contained in all the solutions, increasing its weight to infinity would change the optimal solution and we pick that edge in our solution. Otherwise (if the edge is contained in only some of the solutions) increasing the weight would not change the solution because there is another optimal solution that does not contain that edge so we do not pick that edge.

So we can prove this theorem: At every step of the algorithm if an edge is picked, it is contained in all the optimal solutions.

So the algorithm does not pick any extra edges. Now we have to prove that it includes all the necessary edges. But that is easy because each time that we choose not to including an edge, we are sure that there is an optimal solution in the remaining graph so we are never left with a graph with no optimal solution.

I think you assumed that I meant we change the edge weights from infinity back to their original value at each step but that is not what I meant.

> If the value of the optimal solution has changed it means that the edge must be in the optimal optimization solution.

I interpreted this as meaning you were selecting the falsifying removals' edges, instead of removing the non-falsifying ones. You've got it.

Kind of like proving that you can't solve the halting problem, it lets us put to rest the idea that you can reduce the complexity of NP problems to a deterministic polynomial solution. The collective brainpower can be used to solve other problems.

Intuitively, almost everyone assumes that P != NP but it's been incredibly difficult to prove. If P == NP were proved it would be earth shattering, because lots of difficult problems may become solvable.

> Intuitively, almost everyone assumes that P != NP

Donald Knuth believes P = NP.

Source: http://www.informit.com/articles/article.aspx?p=2213858&WT.m... (question 17). Also cf. https://www.quora.com/Why-does-Donald-Knuth-think-that-P-NP

But keep in mind that he (and just about everyone who believes P = NP) thinks any proof of it will be non-constructive and that we will never actually find a polynomial-time algorithm for NP problems.

Is that really true though? What if someone solves does P equal NP problem by finding a polynomial time algorithm for a problem in NP, but the asymptotic run time is O(n^10^100)?

Sure the race would be on to improve that, but in the meanwhile no difficult problems would become solvable.

related to https://rjlipton.wordpress.com/2010/10/23/galactic-algorithm...

That was really entertaining, thanks for linking it.

I especially liked this bit:

David Johnson famously once said, For any instance {G = (V, E)} that one could fit into the known universe, one would easily prefer {|V |^{70}} to even constant time, if that constant had to be one of Robertson and Seymour’s.

I was curious so I tracked down this:

Johnson estimated that the hidden constant is “somewhat larger” than 2 ⇑ (2 ⇑ (2 ⇑ (h/2)) + 3), where 2 ⇑ t denotes an exponential tower of t 2s (2 ⇑ 0 = 1 and 2 ⇑ t = 2^2⇑(t−1)) and h is the number of vertices in H.

It's generally not the case though: problems that arise 'naturally', i.e have not been constructed to counter my forthcoming point, in P seem to be of low order.

If NPC problems where P in n^{10^100}, wouldn't we expect a wealth of problems between there and the myriad at n^2 or so?

Why would that be more surprising than the fact that some "natural" problems are polynomial and some are exponential, given that an exponential running time is asymptotically slower than any polynomial running time?

Often, just knowing that something is possible can be a catalyst for big advances.

It's easier to get people to devote resources to a hard but solvable problem than to one which may not even be solvable.

This interpretation is wrong. The class P contains for example O(N^(10^100000!)), that are not "solvable" by any remotely reasonable meaning of the word.

This is true, but it's difficult to imagine what such a problem could look like. In reality, algorithms tend to come in discrete complexity "units" with very small terms. A linear algorithm isn't just fast -- it tells you something about how such an algorithm works and thus something important about the problem it solves. A quadratic algorithm can be interpreted as a "considers all pairs from the inputs" algorithm. An n*log(n) algorithm does a divide and conquer step for each input. Moving to the exponential world, you have the 2^n "tries all combinations" and n! "tries all orderings" type algorithms, which again, make sense both as mathematical functions as well as behaviors that constitute sensible algorithms.

What does an O(n^10,000) algorithm do? What understandable problem yields a solution that behaves that way?

To follow up on this, in computational linguistics, there is a sharp divide between facts which take cubic time, like recognizing whether a string belongs to a context-free language, and facts which are halting-problem-hard, like recognizing whether two context-free grammars describe the same language. There doesn't appear to be much of a middle ground.

In another realm of computational mathematics, matrix mjultiplication is cubic, with optimizations that can approach quadratic time with lots of effort. It's conjectured that matrix multiplication can actually be brought arbitrarily close to quadratic time, but at the expense of ever-more-complex algorithms.

It could very well be that the biggest interesting exponent in P is 3 or 4.

The AKS algorithm has been reduced to an exponent of 6. That really strikes me as large for polynomial time algorithms though.

The coupled cluster method CCSD(T), considered the "gold standard" of quantum chemistry, is O(N^7). That's the highest-exponent polynomial time algorithm I'm personally aware of that sees regular use. The various coupled-cluster variants are all basically approximations to full configuration interaction, which is a much worse O(N!).

It is! At first, the following may appear quite counter-intuitive, but if you think about larger N and the fact that you often want efficient algorithms also when processing large amounts of data, it becomes clear that an exponent of 2 or 3 is, in practice, often the most we can realistically handle even when the problem is in P, and even though O(n^2) is extremely low from a computational complexity perspective.

For example, when you have an O(n^3) algorithm and want to process 10,000 elements (which are very few in many situations), it will be, as a rough estimate, 1,000,000,000,000 times slower than processing a single element. This will be acceptable only in very specific situations. As a rule of thumb, an exponent of 2 is already unacceptably slow in many practical situations, and at least on the verge of being unacceptable in others.

That explains why we don't have widely implemented algorithms of higher-degree polynomial complexity, but it doesn't explain why we haven't thought of many such polynomial algorithms that just aren't practical. After all, we can easily name lots of super-exponential algorithms. They're not directly useful for even moderately sized data, but they arise naturally from looking at certain types of problems, so we almost can't help but find them. The same doesn't seem to be true for polynomial algorithms with high degree.

You're essentially referring to the idea that could be loads of high-order poly-time algorithms, but we ignore them because those algorithms are slow, and therefore we don't use them. So in the space of all useful algorithms, we simply have a very biased sample.

I think the truth is more profound than that. There actually don't exist very many interesting* algorithms in the classes O(n^(k>3)). The real world we live in and model does not feature many interesting problems for which high-order polynomial complexity algorithms are natural solutions.

*Not sure what the right word to use here is...maybe non-trivial? The point I'm going for is to say that obviously we can invent an O(n^5) algorithm by simply nesting our loops five-deep and printing something, but that's a constructed example. I'm looking for algorithms that naturally arise as a solution to some problem.

For example, there is 0.8776-approximation that runs in about O(n^{10^100}) https://arxiv.org/abs/1205.0458v2 There are also a lot of graph problems like "distinguish 3-colorable graph from graph that can't be colored in 3 colors even after removing eps part of edges" with large polynomials (IIRC, we got something like O(n^{2^40000}) when tried to find degree explicitly).

While not strictly in the same vein as O(n^10k), the constant factor in the proof that L=SL is 3^(2^65536) at the smallest. A lot of combinatorial problems can generate such algorithms, since they tend to rely on "we can solve this problem if this condition holds, we can make this condition hold for all inputs if we blow up our input with this large structure [which is technically constant time since the structure is fixed and not variant on size!]." Consider that this is the field of mathematics that produced a number that is "3 raised to itself so many times that I need to describe an algorithm just to write that number" that was used as the upper bound to a solution (the lower bound of which was 6).

Your observation about correspondence between algorithmic complexity and its structure seems very interesting to me, thanks for sharing.

Some cryptographic implications on solving the P vs. NP problem or proofing some other stuff on average case complexity: https://www.karlin.mff.cuni.cz/~krajicek/ri5svetu.pdf

In practical terms, a solution to P=NP is very likely to have absolutely no impact on our algorithms, even if the solution is that P=NP. The main utility is in our understanding of complexity theory, and a better understanding of why certain problems, and certain instances of problems, have to be hard.

Let me explain why P=NP probably won't have any impact, since you see a lot of bullshit claiming lots of bad things will happen. The description of complexity classes like P and NP sweep a lot of details under the rug, and those details matter a lot of practical matters.

The more important of these matters is that complexity is based on worst-case running time, not average-case or typical-case. Often times, we can solve most instances of "hard" problems. We can factor most integers, for example--half of them are divisible by 2, and another sixth divisible by 3. If we limit are inputs to factoring products of two primes of roughly equal size, that is difficult. SAT is another example: it may be the canonical NP-complete problem, but many people think nothing of using a SAT solver (or its cousin, the SMT solver) to solve for things like "how do I find an input that can reach this program point." Except if solving that condition requires, say, finding SHA256(x) = binary digits of pi.

This is one of the main cruxes of P?=NP that doesn't come out much: it's not so much that problems are hard or easy, it's that there's this field of problem instances that seem to be intrinsically hard. Indeed, if you look at restricted versions of these NP-complete problems, you'll find that some restrictions still retain NP-complete, but a very slight reduction in those restrictions suddenly admits a very simple, fast, easy solution.

The related notion that you see people sometimes bring up and dismiss is that P and NP hide constants. This objection tends to be dismissed because most people have no familiarity with polynomial-time algorithms with massive constants. But such algorithms do exist, and they tend to crop up in combinatorial-style algorithms. Which, incidentally, is probably what a polynomial algorithm for an NP-complete problem would be.

Let me explain by analogy of a not-so-recently-solved problem that's a weaker but related notion to P?=NP, L?=SL. This question is essentially asking "could you solve every problem that's equivalent to checking for connectivity in an undirected graph using only constant memory" [1]. The answer turns out to be yes. In essence, there is a deterministic string of coin flips deciding your next vertex that will, if followed, eventually guarantee that you will hit every node in the graph that you can reach within a certain amount of time--if your graph has certain properties. And it's possible to transform every graph into one with this property by replacing every node with an expander graph that's only of size 3^2^16 at the smallest. But since the new graph is 3^2^16 * N, that large number is a constant factor that "doesn't matter".

These kinds of constants show up a lot in combinatorial algorithms. All of these algorithms basically have the property that you can solve the input fairly easy if the input has some structure, but to guarantee that the input has that structure, you need to embed it in a very large instance. I argue that, if P=NP were to hold, it would have a similar form to these algorithms. We know that there are some instances that just seem to be intrinsically harder than others, and we know that there are large classes of instances that can be easily solved with fast algorithms. If we haven't been able to generalize the fast algorithms to cover the hard instances but a "fast" (ignoring constants) algorithm must exist, then the apparent complexity has to be generated from sort of fiendish complexity-multiplying, combinatoric structure.

We already see in modern security algorithms that ciphers and hashes have to carefully choose their parameters to make sure they stay in a hard subset of their input algorithms. So even if P=NP, the hard subset is likely to remain much harder than the easy subset, and that gap is sufficient to maintain security.

[1] A very imprecise characterization.

_The Golden Ticket_ is a non-technical book discussing the implications of solving P vs NP

http://goldenticket.fortnow.com/

This is a really nice list of the implications, but breaking public-key cryptography is at the top of the list: https://softwareengineering.stackexchange.com/questions/1488...

I should say, theoretically breaking public-key. In reality the problem may remain too hard to brute force even if the P vs NP problem is solved.

> breaking

This preprint "implies P not equal NP".