Hacker News Reader

Comment by dellamonica | Hacker News Reader

It seems that your assumption is that there could be an efficient algorithm that can analyze any program with a bounded number of states and check that it halts.

However, it is simple to show that this is at least as hard as NP complete. For instance, you can map the Hamiltonian cycle problem to a halting problem over programs that do an infinite walk on graphs without a Hamiltonian cycle and those that stop whenever they complete a walk along a Ham cycle.

At this time P vs NP is still wide open and, in general, statements in complexity theory are usually dependent on some unproven hypothesis so I still don't understand what is your point exactly.

View on HN

Yes, exactly, you seem to be understanding my point: there could be an efficient algorithm that can analyze any program with a bounded number of states and check that it halts.

Among other things, because the P vs NP issue is still wide open, yes.

I'd just like to add three more minor points:

1. Many people believe the above to be false, because they believe that the problem is undecidable also for programs with a bounded number of states.

2. That I would like if more people focused on finding such an efficient algorithm.

3. And that I think that even some people who believe that the problem is decidable think that it's impossible to have an efficient algorithm because of the Halting problem and Rice's theorem, which formally speaking, neither of them say anything about whether such efficient algorithms exist or not.

To be honest, I doubt that people who can actually make any progress in these areas would fail to know already what you are saying.

The P vs NP question is open but the conditional results are not merely novelties. There are many results that show very weird consequences for having P=NP. So either the nature of computing is utterly bizarre or in fact there are many common problems which are simply impossible to solve exactly in a reasonable amount of time.

You can of course try to find good heuristics that cover some common cases or even approximations of NP hard problems in some cases. There are literally thousands of researchers doing that every day.

> To be honest, I doubt that people who can actually make any progress in these areas would fail to know already what you are saying.

I hope you are correct :-)

> There are many results that show very weird consequences for having P=NP. So either the nature of computing is utterly bizarre or in fact there are many common problems which are simply impossible to solve exactly in a reasonable amount of time.

Wow, that's very interesting! Can you recall an example or two of such consequences? I would be really interested in reading about that.

Edit: Donald Knuth seems to believe that P=NP and also says there would be no major implications if we found such a proof...

> You can of course try to find good heuristics that cover some common cases or even approximations of NP hard problems in some cases. There are literally thousands of researchers doing that every day.

Completely agreed!

Perhaps you are right and my worries are unfounded.

Here is an interesting discussion about the relation to EXP and circuit complexity. https://mathoverflow.net/questions/58201/why-is-p-np-implies...

A nice presentation by Wigderson may also help to see consequences of P=NP in a less rigorous phrasing ("'Creativity' can be efficiently automated [if P=NP]"). https://view.officeapps.live.com/op/view.aspx?src=https%3A%2... There is a more formal text as well: https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/W06/w06....

Another class of results that I find interesting are inapproximability results. Namely, for certain NP hard problems, it is impossible to have a polynomial algorithm that computes the right value (for all instances) within a certain approximation factor unless P=NP. In https://dl.acm.org/doi/10.1145/1132516.1132612 Zuckerman shows that approximating MAX-CLIQUE is hopeless unless P=NP.

This is of course just a mountain of evidence and not a proof. It does mean that there are potentially many ways in which one could prove P=NP without necessarily achieving anything practical. This is what I think Knuth means: you could have a non-constructive proof of P=NP or perhaps an algorithm with complexity n^10^10^10 that solves an NP-complete problem.

Reply on news.ycombinator.com