Comment by rssoconnor | Hacker News Reader

Comment by rssoconnor | Hacker News Reader

In my experience, I find that constructive mathematics better aligns with peoples intuitions here rather than classical computer science.

For example, we don't (yet) have a proof that there exists (constructively) a program that that prints out the answer to the P=NP problem.

I had some commentary in my thesis about this issue with regards to computable Julia sets. Mark Braverman proved that every (quadratic) Julia set is computable. But, as he notes, his proof isn't uniformly computable. Instead he develops 5 machines that attempt to draw various sets (at whatever desired resolution) given the parameter for the Julia set desired. For each Julia set, one of these 5 machines will correctly draw the set.

When doing constructive mathematics, the constructive notion of a compact set roughly corresponds to being a computable set in the sense we need for computable Julia sets. We cannot constructively prove that every (quadratic) Julia set is compact. Instead we have to divide the complex plane of possible parameters of the Julia set into multiple regions, and within each of those regions we can prove all of the corresponding Julia sets are compact.

In classical mathematics the union of all these regions is the entire complex plane, but this result doesn't hold constructively. Analogously, in classical mathematics the union of the positive reals, and the non-positive reals is the whole real line; however, again, this result doesn't hold constructively.

The constructive mathematics approach clearly states exactly what additional information is need to actually realize the computation of a (quadratic) Julia set: that is you must state in which of these regions of the complex plane you given parameter belongs to, which in turn tells you which of these 5 machines you need to run to get actually get the image you want. This is a much more satisfying answer.

And in the P=?NP case Aaronson uses, the answer wouldn't be "P=NP" (a classical answer -- totally useless) but the actual function NP->P.

People just instinctively know that you need to know which side of the disjunction you're on, and they haven't been trained in classical logic to forget it.

If NP somehow was proved to be P, with a likely value being something like O(n^(10^10^10)) or much larger, would the actual constructive reduction be at all useful?

We already have such a machine. If P=NP then there is some Turing machine that produces, for instance, a 3-SAT certificate in polynomial time.

We may enumerate the turing machines and call ours the M-th one. Given a boolean expression P, increment a counter N and run the first N turing machines on P for N steps, check each of the outputs of these against the certificate checker.

If M runs in time O(|P|^n) and the certificate checker is O(|C|^m) and then our hybrid machine runs in something like O((M+|P|^n)^2m).

All we're missing is a proof.

My point is that N is most probably bigger than the entire Universe, if it turns out to be finite.

> For each Julia set, one of these 5 machines will correctly draw the set.

That's really interesting. Does this essentially correspond to a proof of being able to compute the correct set with probability no less than 1/5?

For the question "which of the 5 is correct?", is it presumed that there exists a proof that hasn't been found yet or that this is undecidable (e.g., within ZFC)?

> For the question "which of the 5 is correct?"

There is a discontinuity as the parameter 'c' crosses a location that lies on the boundary of the Mandelbrot set, where the corresponding Juila set goes from a thick ring of disconnected points (Cantor-set like) to suddenly connected and the ring is completely filled in. One candidate machine will draw a filled in Julia set, and another candidate machine will draw the ring.

For each Turing Machine one can construct a complex value c, that is just barely outside the Mandlebrot set if the machine halts, but is on the inside (specifically on the boundary) of the Mandelbrot set if the Machine does not halt.

Thus being able to correctly draw the Julia set all of these points amounts to solving the halting problem. Though any individual point may or may not be solvable.

Of course there is at least one Turing Machine that searches for an inconsistency in ZFC. If ZFC is consistent then this machine never halts, but ZFC cannot prove this fact.

Reply on news.ycombinator.com