[bhrgunatha]

Yes, this always confuses me. Why the constants are swept under teh carpet for real world, practical applications. From the same article.

"It is also possible that a proof would not lead directly to efficient methods, perhaps if the proof is non-constructive, or the size of the bounding polynomial is too big to be efficient in practice."

Given the long standing nature of the problem, my guess is that some new techniques or insights will be required to solve it one way or the other. Those may well give clues to solving NP/NP-Complete problems efficiently.

Until someone actually does it though it's still just speculation.

[smallnamespace]

One answer is because in practice, we very rarely see large constants anywhere. While theoretically x^1000 algorithms exist, it's hard to actually find a reasonable example of one. Ditto for e^1.00000001.

Of course, why this might be the case remains to be investigated.

[adrianN]

Example: You want to bisect the nodes of an edge-weighted graph into two sets of equal size such that the sum of the edge weights between the two parts is maximized.

The best approximation algorithm (it's NP-hard) runs in time O(n^(10^100)):

https://arxiv.org/pdf/1205.0458v2.pdf

For more examples see here http://cstheory.stackexchange.com/questions/6660/polynomial-...

[smallnamespace]

It's interesting though that the examples you provided are all approximations for known NP-hard problems, and in many cases the free parameter that lets you get arbitrarily large constants depends on how close to optimal you want the approximation to be.

Do you have examples of large-constant algorithms in P that are not approximations of NP-Hard problems?

[vitus]

Not quite the same as the earlier conversation on exponents, but since you mentioned constants, matrix multiplication is a prime example -- apparently Coppersmith-Winograd has enormous constants ("only provides an advantage for matrices so large that they cannot be processed by modern hardware") that I can't find them (the wiki article doesn't really have a proper source, and preliminary searching also yielded no concrete results -- possibly because the proof of existence was non-constructive?).

[fmap]

Complexity theory abounds with such algorithms in order to solve concrete problems. In fact it's even worse than that. There is a whole subfield of complexity theory which looks for "fixed-parameter tractability" and typically involves algorithms with reasonable exponents but astronomical constants. Even if you have an O(n) algorithm, if the constant hidden by the notation happens to be on the order of 10^10000 this is not something that you could ever hope to run.

One example are all the consequences of the Robertson-Seymour theorem which (non-constructively) asserts that a large number of graph problems "is in P". For instance, we know that testing whether a graph can be embedded in the torus is in P, but the algorithm in question is completely infeasible.

I would expect a positive answer to P = NP to be completely useless in practice. A negative answer would similarly be rather unexiting by itself. What would be exiting are the tools for getting this answer...

[btilly]

The "non-constructively" in this case has fascinating consequences.

One of those is that according to classical mathematics there are concrete problems with polynomial time algorithms that there is no way of producing, and if produced, there is no way of verifying. (Literally no way of verifying, pick an axiom system and there are problems for which the question of whether there is one more forbidden minor is undecidable in said axiom system.)

If you doubt that such algorithms have any real existence, you might be a closet constructivist...

[rhaps0dy]

>I would expect a positive answer to P = NP to be completely useless in practice. A negative answer would similarly be rather unexiting by itself. What would be exiting are the tools for getting this answer...

That's basically Donald Knuth's position. http://www.informit.com/articles/article.aspx?p=2213858

[Ar-Curunir]

Fixed parameter tractability is not necessarily about polynomial time algorithms with huge constants; it's about getting efficient algorithms for problems that have different parameters. Optimising over all the parameters might require exponential time, but if you fix one of the parameters, some problems become tractable (with the constant depending on the value of the fixed parameter).

This can lead to large constants, but doesn't have to. It depends on the value of the fixed parameter.

[btilly]

In this case the polynomial time algorithm is to test the graph against a finite list of forbidden minors. This has a reasonable exponent, but a constant dependent upon how long that finite list is.

That finite list can be extremely long indeed. And in some cases, there is no way of finding or verifying the full list.

[taeric]

Do we rarely see large constants? Or are they just not on problems where precision and "absolute best answer" matter?

As an example, an algorithm to find the optimal solution to a Rubik's cube would actually be very difficult to do. However, finding a solution in a short enough time frame is quite easy. This is more true the larger of a cube you try and solve.

Contrast this with problems such as encryption, where we have specifically made problems where there is not a "best answer", but rather there is only a single answer that matters.

[smallnamespace]

I think you're proving my point here -- finding the optimal solution for a Rubik's cube is probably at least PSPACE-Hard, which is probably exponential.

So complexity theory is confirming your intuition, which is that 'optimization type problems' are hard.

[dom0]

Even the basic rucksack optimization problem is NP-hard. I'd dare say that a huge class of optimization problems maps very naturally to this particular one, https://news.ycombinator.com/item?id=13316776 for starters.

[taeric]

Ok, so optimization problems are potentially bounded with smaller coefficients than we would think.

What about sequencing life? Supposedly we share a lot at the genomic level with animals we are vastly different from. Could a large degree of the polynomial that is life explain that divergence?

[dom0]

What?

[taeric]

I misunderstood your point, then. I thought you were saying that we rarely see giant exponents in things. My question is if we typically do see giant exponents, but make do with much simpler solutions. (That make sense?)

[smallnamespace]

I am saying we rarely see giant exponents (on polynomial-time algorithms) in practice, because most algorithms that we intuitively think of as 'hard' turn out to be in NP or PSPACE or other complexity classes that we have decent reason to suspect have a lower-bound exponential running time.

[taeric]

Sadly, I'm not sure I understand the point. Aren't we saying these could be exponential, just with large coefficients?

Edit: I meant "small" coefficients above. Apologies.

[Smaug123]

Aaronson specifically addresses this in section 1.2.1, on page 6.

[bhrgunatha]

To be clear I'm not talking about how useful asymptotic analysis and big O notation are in general, I'm talking specifically about the case if we eventually do prove P = NP.

Internet lore and popular media then assume that immediately for example all encryption will be trivially broken. Mathematically it may be true because then all NP problems would be known to be polynomial, but there's still the issue of the practical steps involved factorising a huge number which may have enormous constants or very large exponents. Or if it turns out we can reduce it to some other known polynomial problem, there's still the actual transformation which itself may be polynomial with large constants or exponents.

[smitherfield]

If I'm not mistaken, isn't it also the case that factorization hasn't been proven to be in NP?

[teraflop]

That's not quite correct. Factorization is definitely in NP, because verifying whether a number has a particular factor is easy.

Maybe you meant that factorization hasn't been proven to be NP-complete, which is true. In fact it would be very surprising if it was NP-complete, because that would imply other surprising things (e.g. NP = co-NP).

[Beltiras]

If P=NP is proven than that makes factorization an easy problem (and included in the proof) which would make many algorithms for encryption "trivially broken".

[lomnakkus]

Right, but it's worth mentioning that factorization itself is not known to be NP-hard (and it's suspected not to be, by most, I think).

Also, as others have pointed out, the constants involved in any "generic" algorithm for solving any NP problem in Polynomial type may be astronomical, so even if it turns out that P=NP, then it may not ever be feasible to actually such any algorithm for anything practical.