dellamonica

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.

Implemented in this context means exactly the type of reduction that is needed. If halt can be implemented by using X that means you can reduce X to halt. This is similar to polynomial time reductions in complexity.

Standard practice in mathematics would apply here if what was said is wrong. This time it is about an interpretation that no one shares with you.

[edit] After reading again your comment I realized that maybe you are not applying the logic correctly. If the reduction "implementation" uses both length and foo, then the conclusion is that at least one of length or foo cannot be computable. Since length is trivial, then it must be foo that is not computable.

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.

Wait, so you are saying that the only thing missing in the first statement is that the implementation is required to be correct?

I think that is pretty obvious. This is beyond nitpicking.

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.

Basically, everything that a regular graph is known to contain will also be present in this broad class of graphs (by simple inclusion).

This is enough to establish some results like Thomassen's, that is, containing a sub-graph of minimum degree >= \delta and "girth" >= g (where you need the degree of the regular graph to be large enough in terms of \delta and g).

*girth of a graph is the length of the smallest cycle (a triangle is a cycle of length 3).

It is quite nice see that our [D-V.Rödl] bound on Thomassen's conjecture stood for over a decade, but I always felt that it would be improved to at least what Janzer and Sudakov now show.

In fact, in our paper we show the log(log(Delta)) bound assuming that G is C4-free, now you can get this (and much more) without assuming structure on G. Fantastic!

Linear Programming methods (barrier/simplex) have been able to run faster and solve larger instances in great part due to algorithmic advances (the other contribution being faster hardware, more memory etc). Considering that LP is a fundamental tool for mixed/integer programming, these improvements are incredibly valuable.

Gurobi had a white paper mentioning how much their solvers' performance was improved by which techniques (I'll link it here if I can find it).

They are working on Native AOT for .net 7, which is based on CoreRT. See the issues tracked in the runtime repo.

I have been using it with reflection fully disabled in a console app and it produces a 5Mb native binary.