[FRIAM] a limit to verificationist inquiry

[jon zingale]

At the end of vFriam last week, I prompted a discussion about a possible
relationship between *zero-knowledge protocols* (zkp) and a limit to
scientific truth interpreted as a strict verificationist theory[1].
Neal Koblitz gives an accessible explication of a zkp 3-colorability
proof[2], which I attempt to summarize here.

A graph is 3-colorable if we can paint each of its nodes with only three
colors in such a way that no two adjacent nodes have the same color.
Now given a prover and a verifier, let's call them Bruce and Nick, a zkp
will provide a means for Nick to verify Bruce's proof without Bruce
needing to provide any information about his proof.

Paraphrasing Koblitz, Bruce hands Nick a graph where each node is a light
in the off state. When Nick grabs an edge, the endpoint nodes (and only
the endpoint nodes) light up exposing that these nodes are colored
differently. When Nick let's go of the edge, each color experiences a
random permutation, resetting all vertices accordingly. Nick is then free
to grab another edge, repeating his liberty to choose until he has seen
every edge.

Now, if Bruce did not have a 3-coloring then he wouldn't be able to fool
Nick (eventually Nick will grab an edge whose endpoints are the same).
Also, Nick has learned nothing about the coloring except for the fact
that Bruce has a valid 3-coloring.

In Koblitz's explication, he imagines that the prover prefers to keep the
solution from the verifier, but it could very well be that mechanics
prevent the prover from sharing with the verifier. It may be that the
permutations are effected by a demon in between, a fact of the world
where actions are limited to those described above. This is to say, it
may be the case that Bruce has knowledge that Nick can verify, but whose
nature Bruce cannot express. While Nick can determine the existence of
such knowledge, it may be provable that Nick's inquiries will not further
him in his determination of *the Truth*. Of course, the real-life Nick is
likely Ok with this outcome. It can be the case that he and Bruce converge
on the existence of such a graph coloring (certifying the fact as *True*),
and yet the production of such a coloring would remain outside the scope
of truth.

-- speculation warning --
What fascinates me at the moment is the possibility that constructions
like this are ubiquitous. We may discover that something like this is
the case for Goldbach's or Collatz's conjecture, cases where the problem
statements are so thin that agency to prove is somehow provably limited.
We may find it provable that a proof exists, but the construction of such
a proof does not. Perhaps in physics, we will discover an entanglement-
like property for electrons that implies a 2-coloring graph over spin,
but where measurement behaves like the randomizing demon above.

[1] A theory of knowledge where only statements verifiable through direct
observation or logical proof is meaningful.

[2] http://almuhammadi.com/sultan/crypto_books/Koblitz.2ndEd.pdf 118-119




--
Sent from: http://friam.471366.n2.nabble.com/