dellamonica

6 ms·

31.
by dellamonica 4y ago
You would need to show how to use length to implement halt and that is the part you will not be able to do. If you did, then yes, length would not be computable. Reductions in complexity theory work like this. An explicit algorithm invoke
32.
by dellamonica 4y ago
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 consequence
33.
by dellamonica 4y ago
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 mat
34.
by dellamonica 4y ago
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 th
35.
by dellamonica 4y ago
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.
36.
by dellamonica 4y ago
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. Fo
37.
by dellamonica 4y ago
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 mini
38.
by dellamonica 4y ago
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
39.
by dellamonica 5y ago
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 fu
40.
by dellamonica 5y ago
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.