logoalt Hacker News

chonglitoday at 1:50 AM4 repliesview on HN

A proof by contradiction that p = np is of no use to anyone, given that it wouldn't help you find any polynomial time algorithms for np-hard problems.


Replies

ziiinqtoday at 3:30 AM

I don’t recall anything specific off the top of my head but I am confident that such a proof would have immediate actionable implications.

Furthermore, careful analysis of the latter would as likely as not yield further understanding and, actually /would/ help finding such algorithms.

Finally, it has been observed time and time again that often (again, nothing comes up and i don’t want to ask AI) the certainty that something is possible and has been done is motivation and inspiration enough for people to independently solve a problem. Sometimes it is even enough for someone new to simply not know that something is “hard” to solve.

It even “motivates” llms, it seems (eg https://cdn.openai.com/pdf/04d1d1e4-bc75-476a-97cf-49055cd98...)

Of course this is all pure speculation concerning a hypothetical proof that most likely doesn’t exist, or indeed might be so complicated as to not be approachable even after hundreds of lifetimes of study.

Nevertheless your conclusion does not follow from the premise

shakowtoday at 10:57 AM

I don't think a proof that P = or ≠ NP would give you any polynomial-time algos for arbitrary problems either.

zmgsabsttoday at 4:06 AM

Abstract polynomial algorithms are of no use either, eg, translation may require galactic constants or high powers that are still intractable.

We only compute with two kinds of things:

- small data; or,

- extremely lower power and coefficient algorithms

We lack the power to, eg, use a quintic algorithm in anything but nearly trivial cases.

Jenssontoday at 4:00 AM

A proof that they are the same is of no use either, since it too wouldn't help you find algorithms that are faster.

You would need an algorithm that finds solutions, not just a proof they exist. So the value here would almost entirely come from how you proved p = np, since that proof will probably be the first step towards finding the polynomial solutions. But if humans don't understand it good luck finding any.