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/

- .... . -..-. . -. -.. -..-. .. ... -..-. .... . .-. .
FRIAM Applied Complexity Group listserv
Zoom Fridays 9:30a-12p Mtn GMT-6  bit.ly/virtualfriam
un/subscribe http://redfish.com/mailman/listinfo/friam_redfish.com
archives: http://friam.471366.n2.nabble.com/
FRIAM-COMIC http://friam-comic.blogspot.com/ 

[thompnickson2]

Hi, Jon,

Let's see if we can get this on the agenda this morning.   I don't yet
understand a word, so you may have to proceed slowly, because others may be
in the same boat.  One question that might need mulling:  is falsification a
kind of verificationist inquiry?  Or  does your thinking lead to Popper's
conclusion that theories can only be falsified.  If so, you challenge
Peirce's assertion that abduction is a form of valid reasoning, if
probabilistic.  

Nick

Nicholas Thompson
Emeritus Professor of Ethology and Psychology
Clark University
[hidden email]
https://wordpress.clarku.edu/nthompson/
 


-----Original Message-----
From: Friam <[hidden email]> On Behalf Of jon zingale
Sent: Friday, January 8, 2021 1:08 AM
To: [hidden email]
Subject: [FRIAM] a limit to verificationist inquiry

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/

- .... . -..-. . -. -.. -..-. .. ... -..-. .... . .-. .
FRIAM Applied Complexity Group listserv
Zoom Fridays 9:30a-12p Mtn GMT-6  bit.ly/virtualfriam un/subscribe
http://redfish.com/mailman/listinfo/friam_redfish.com
archives: http://friam.471366.n2.nabble.com/
FRIAM-COMIC http://friam-comic.blogspot.com/ 


- .... . -..-. . -. -.. -..-. .. ... -..-. .... . .-. .
FRIAM Applied Complexity Group listserv
Zoom Fridays 9:30a-12p Mtn GMT-6  bit.ly/virtualfriam
un/subscribe http://redfish.com/mailman/listinfo/friam_redfish.com
archives: http://friam.471366.n2.nabble.com/
FRIAM-COMIC http://friam-comic.blogspot.com/