0
$\begingroup$

I've seen arguments for $P \ne NP$ that rely on certain intuitions about how the real world actually is, generally making the point that it "makes sense" that there exist problems which have an easily verifiable solution that's hard to find.

For example, on his blog, Scott Aaronson has a "Reasons to believe" entry which contains (among others) the following points:

8. The Self-Referential Argument. If P=NP, then by that very fact, one would on general grounds expect a proof of P=NP to be easy to find. On the other hand, if P!=NP, then one would on general grounds expect a proof of P!=NP to be difficult to find. So believing P!=NP seems to yield a more ‘consistent’ picture of mathematical reality.

9. The Philosophical Argument. If P=NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in “creative leaps,” no fundamental gap between solving a problem and recognizing the solution once it’s found. Everyone who could appreciate a symphony would be Mozart; everyone who could follow a step-by-step argument would be Gauss; everyone who could recognize a good investment strategy would be Warren Buffett. It’s possible to put the point in Darwinian terms: if this is the sort of universe we inhabited, why wouldn’t we already have evolved to take advantage of it? (Indeed, this is an argument not only for P!=NP, but for NP-complete problems not being efficiently solvable in the physical world.)

10. The Utilitarian Argument. [$^1$] Suppose you believe P!=NP. Then there are only two possibilities, both of which are deeply gratifying: either you’re right, or else there’s a way to solve NP-complete problems in polynomial time. (I realize that I’ve given a general argument for pessimism.)

But the way I see it, once you step down from the abstractions of complexity theory and start talking about actual reality, then the concept of "polinomiality" seems to lose most of its weight and $P$ feels unimportant. Instead of supporting the idea that $P \ne NP$, these arguments could just as well merely support the idea that any $NPC$ problem has a lower-bound of $\Omega(n^k)$, for a decently sized $k$.

But I am not an expert, so I am missing some context; for example, nuanced analyses of "real" algorithms on "real sizes" of inputs. So is there something more to the robustness of this kind of arguments, or are they overblown?


$^1$ point 10 is worded in such a way that doesn't really fit my selection, but I feel that in the given context, the author did intend to conflate "solve in polynomial time" with "feasibly solve", hence why that would be gratifying.

$\endgroup$
6
  • $\begingroup$ Does this answer your question? What would be the real-world implications of a constructive $P=NP$ proof? $\endgroup$
    – Dmitry
    Aug 21, 2022 at 23:36
  • $\begingroup$ @Dmitry well, partly. Some answers there claim that it is indeed a reasonable assumption that if $P = NP$, there could be $NPC$ problems with a very high degree polynomial (or just with large constants). So these problems wouldn't be "feasible" in a practical sense. $\endgroup$ Aug 23, 2022 at 8:04
  • 1
    $\begingroup$ Please link to the source you are copying from. We require that you provide proper credit for all copied material, including linking to the original page: cs.stackexchange.com/help/referencing $\endgroup$
    – D.W.
    Sep 21, 2022 at 23:28
  • $\begingroup$ I don't see a clear connection between the title and the post. What is your question ? $\endgroup$
    – user16034
    Jan 10, 2023 at 14:41
  • $\begingroup$ The "polynomial" vs. "non polynomial" characteristics are non-negotiable. A non-polynomial function amounts to a polynomial of infinite degree. This distinction has nothing to do with practice, as it usually relates to astronomical numbers. It is conceptual. By the way, I don't remember having seen polynomial times of real-life algorithms that exceeded $O(n^{10})$. $\endgroup$
    – user16034
    Jan 10, 2023 at 14:45

4 Answers 4

1
$\begingroup$

The $P/NP$ conjecture is about theoretical complexity classes. It is not about practical running times. You cannot run a $\Theta (n^{10})$ algorithm on with $n=40$ elements in reasonable time, and you can very well run a $\Theta(2^n)$ algorithm with $n=40$.

The distinction is more qualitative than quantitative, and the border is neat.


Said differently, if you push a polynomial algorithm to the largest $n$ that can be handled in your time frame, in general $n+1$ won't make a real difference. For an exponential or super-exponential algorithm, $n+1$ could be out of reach.

$\endgroup$
1
  • $\begingroup$ @JohnL.: $40^{10}\gg2^{40}$. $\endgroup$
    – user16034
    Feb 10, 2023 at 15:52
0
$\begingroup$

Why do some "common sense" ... arguments ...

I'm not sure if this question is on topic here, however ...

"Common sense" arguments often lead to completely wrong results:

This is not only the case for proofs but also for estimations of values that are only very difficult to calculate. The birthday paradox is one example for this.

And the arguments you cited do not only disregard high-order polynomials (like $\Omega(n^{1000})$) but they already don't work for $\Omega(n^1)$:

Argument 8 for example assumes that some $\Omega(n)$ task is "easy" if it is easy to prove the correct result.

However, both German and English languages even have a proverb based on a counterexample:

Finding a needle in a haystack ...

... has a time complexity of $\Omega(n)$ and proving the "positive" result is very easy.

$\endgroup$
1
  • $\begingroup$ Easy and sometimes painful :-) $\endgroup$
    – gnasher729
    Aug 22, 2022 at 21:11
0
$\begingroup$

Of course it is a possibility that $\mathrm{P} = \mathrm{NP}$, and the best algorithm for SAT takes $O(n^{1000!})$. However, this feels much weirder than having an $O(n^3)$ algorithm for SAT (with reasonable coefficients). The reason for this feeling weird is the following heuristic:

Naturally occurring natural numbers tend to be $0$, $1$ or $2$, but at most $4$.

Obviously, this doesn't apply to all fields, but it works out quite well for complexity theory and adjacent fields. For example, when we do find a polynomial-time algorithm for an interesting problem, it really tends to have at most cubic runtime. For kSAT, only the $k = 1,2,3$ cases really matter. Planar graphs are special, but we don't care about whether a graph embeds into $\mathbb{R}^{10}$ or not. In computability theory, interesting problems are decidable, equivalent to the Halting problem or equivalent to the Halting problem iterated once. Once we talk about stuff computable relative to $\emptyset'''''$ it has gotten very weird.

$\endgroup$
3
  • $\begingroup$ Do you have any reference for that "heuristic"? $\endgroup$
    – Nathaniel
    Jan 10, 2023 at 14:20
  • $\begingroup$ Also reminder: the first algorithm to prove that $\texttt{PRIMES}\in \mathsf{P}$ was in $\mathcal{O}(n^{12})$. $\endgroup$
    – Nathaniel
    Jan 10, 2023 at 14:31
  • 1
    $\begingroup$ @Nathaniel I don't really have a reference for this, my belief that this is a common stance is just based on talking to people. And the PRIMES in P stuff was definitely weird, wasn't it? $\endgroup$
    – Arno
    Jan 10, 2023 at 14:34
-1
$\begingroup$

It seems that all the mass in the universe, converted to energy, is not enough to perform $2^{256}$ state changes. So an $n^{256}$ algorithm cannot even finish for n = 2.

But assume we find an algorithm that solves instances of size n in $n^{10}$ nanoseconds. Then we can solve instances of size 8 in a second, size 25 in a day, size 45 in a year, size 340 in a billion years.

So we would have a polynomial algorithm that isn’t really satisfactory. A $2^n$ nanosecond algorithm could solve problems of size 30 in a second, 46 in a day, 55 in a year, 85 in a billion year. This exponential time algorithm beats the $n^{10}$ algorithm for cases taking many years.

So even moderately high degree polynomials are not really helpful in many cases.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.