<p>The <span class="math-container">$NP$</span>-problem here is not the problem of finding y,z,n, but rather the following problem:
&quot;Given a mathematical statement <span class="math-container">$A$</span> that can be encoded in <span class="math-container">$n$</span> bits, does there exist a proof of <span class="math-container">$A$</span> in Peano arithmetic that can be encoded in <span class="math-container">$p(n)$</span> bits?&quot; where <span class="math-container">$p$</span> is some arbitrary fixed polynomial and the particular encoding is chosen in advance.</p>
<p>This problem is clearly an <span class="math-container">$NP$</span>-problem, since it is possible to design a polynomial-time Turing machine that takes as an input <span class="math-container">$A$</span> and a candidate proof <span class="math-container">$P$</span>, and says accepts iff <span class="math-container">$P$</span> is a valid proof of <span class="math-container">$A$</span>. Therefore, there is a way to map every statement <span class="math-container">$A$</span> into a graph <span class="math-container">$G(A)$</span> that is <span class="math-container">$3$</span>-colorable iff <span class="math-container">$A$</span> has a proof of length at most <span class="math-container">$p(n)$</span>.</p>

CC BY-SA 4.0
2022-08-02T12:31:40.633Z
2022-08-02T12:31:40.633Z
Or Meir
<p>I'll preface this question by saying I have very little (zero!) knowledge of theoretical computer science, and this post is a genuine attempt to understand something, even if at an intuitive level, which lies quite far from the field in which I work. Please forgive the amateurish wording and feel free to edit as appropriate.</p>
<p>In <a href="https://www.youtube.com/watch?v=5ovdoxnfFVc" rel="nofollow noreferrer">this</a> numberphile video from several months ago, Avi Wigderson explains the idea behind <a href="https://people.csail.mit.edu/silvio/Selected%20Scientific%20Papers/Zero%20Knowledge/Proofs_That_Yield_Nothing_But_Their_Validity_or_All_Languages_in_NP_Have_Zero-Knowledge_Proof_Systems.pdf" rel="nofollow noreferrer">this</a> 1991 paper of his with Goldreich and Micali in layman terms: define a mapping from mathematical statements to graphs, such that every 3-coloring of the output corresponds to a proof of the input. As an abstract example, he gives Fermat's last theorem (FLT), whose statement happens to be very simple one in Peano arithmetic but is very difficult to prove.</p>
<p>The paper, however, says that the mathematical statement must lie in NP (and also mentions CNF formulas). The only way I can think of of transforming FLT into a decision problem is something along the lines of <span class="math-container">$\not \exists x,y,z,n \in \mathbb N, \ n &gt; 2, \ x,y,z,n \leq M \ x^n + y^n = z^n$</span> where <span class="math-container">$M \in \mathbb N$</span> is the input. While this is obviously in coNP, I cannot see why it should be in NP (what's a certificate for <span class="math-container">$M$</span>?). Also, this should be proved for all <span class="math-container">$M$</span>, so does this mean the resulting graph would have to be infinite? And finally, if the graph has infinite edges, I don't see how the zero-knowledge mechanism can work with arbitrary accuracy, since I could have a faulty proof that yields a colouring which fails on finitely many edges, and I would get caught with zero probability (at least if each check only consists of one/finitely many edges as described in the video).</p>
<p>I get that FLT is mentioned a little tongue-in-cheek, and perhaps I'm taking the claim a little too literally, but I also find it strange that Wigderson would make it without issuing any sort of caveat if it is indeed the case that the paper only applies to formulas involving only <span class="math-container">$\neg, \vee, \wedge$</span>. I would be very grateful if someone familiar with this material could clear up my confusion.</p>

CC BY-SA 4.0
2021-12-24T21:27:16.313Z
(1) The transformation in question is not of FLT into a decision problem, but the proof of FLT into one. That is, $L$ is the set of all (encodings of) valid mathematical statements for which there exists a (standard) proof of length bounded by some fixed polynomial in the statement length, and we want to find out if $x\in L$ where $x$ is an encoding of the statement of FLT. (2) I don't think any reduction should have infinite edges since it takes place in polytime. As long as it's polynomial, a (different) polynomial number of color reshufflings and edge queries can get you to 1-ɛ soundness.
Yonatan N
CC BY-SA 4.0
2021-12-26T09:54:07.020Z
Thanks for your comment. Maybe I misunderstood the video then: I thought he was defining (roughly speaking) mappings $G \colon \{\text{mathematical statements}\} \to \{\text{graphs}\}$ and $P_s \colon \{\text{proofs of } s\} \to \{3\text{-colorings of } s\}$ for statements $s$. If $G(\text{FLT})$ were a finite graph, this would mean we can check whether it holds true through a finite search, which seems very strange. What am I getting wrong?
Emilio Ferrucci
<soft-question><graph-colouring><interactive-proofs><zero-knowledge><cryptography>
Graph associated to a mathematical statement (for the purpose of zero-knowledge proofs)
Emilio Ferrucci
# Graph associated to a mathematical statement (for the purpose of zero-knowledge proofs)

(Asked by: username_0 on 2021-12-23)

I'll preface this question by saying I have very little (zero!) knowledge of theoretical computer science, and this post is a genuine attempt to understand something, even if at an intuitive level, which lies quite far from the field in which I work. Please forgive the amateurish wording and feel free to edit as appropriate.

In [this](https://www.youtube.com/watch?v=5ovdoxnfFVc) numberphile video from several months ago, Avi Wigderson explains the idea behind [this](https://people.csail.mit.edu/silvio/Selected%20Scientific%20Papers/Zero%20Knowledge/Proofs_That_Yield_Nothing_But_Their_Validity_or_All_Languages_in_NP_Have_Zero-Knowledge_Proof_Systems.pdf) 1991 paper of his with Goldreich and Micali in layman terms: define a mapping from mathematical statements to graphs, such that every 3-coloring of the output corresponds to a proof of the input. As an abstract example, he gives Fermat's last theorem (FLT), whose statement happens to be very simple one in Peano arithmetic but is very difficult to prove.

The paper, however, says that the mathematical statement must lie in NP (and also mentions CNF formulas). The only way I can think of of transforming FLT into a decision problem is something along the lines of $\not \exists x,y,z,n \in \mathbb N, \ n > 2, \ x,y,z,n \leq M \ x^n + y^n = z^n$ where $M \in \mathbb N$ is the input. While this is obviously in coNP, I cannot see why it should be in NP (what's a certificate for $M$?). Also, this should be proved for all $M$, so does this mean the resulting graph would have to be infinite? And finally, if the graph has infinite edges, I don't see how the zero-knowledge mechanism can work with arbitrary accuracy, since I could have a faulty proof that yields a colouring which fails on finitely many edges, and I would get caught with zero probability (at least if each check only consists of one/finitely many edges as described in the video).

I get that FLT is mentioned a little tongue-in-cheek, and perhaps I'm taking the claim a little too literally, but I also find it strange that Wigderson would make it without issuing any sort of caveat if it is indeed the case that the paper only applies to formulas involving only $\neg, \vee, \wedge$. I would be very grateful if someone familiar with this material could clear up my confusion.

**Tags:** soft-question, graph-colouring, interactive-proofs, zero-knowledge, cryptography
> **Comments:**
> **username_1**: (1) The transformation in question is not of FLT into a decision problem, but the proof of FLT into one. That is, $L$ is the set of all (encodings of) valid mathematical statements for which there exists a (standard) proof of length bounded by some fixed polynomial in the statement length, and we want to find out if $x\in L$ where $x$ is an encoding of the statement of FLT. (2) I don't think any reduction should have infinite edges since it takes place in polytime. As long as it's polynomial, a (different) polynomial number of color reshufflings and edge queries can get you to 1-ɛ soundness.  
> **username_0**: Thanks for your comment. Maybe I misunderstood the video then: I thought he was defining (roughly speaking) mappings $G \colon \{\text{mathematical statements}\} \to \{\text{graphs}\}$ and $P_s \colon \{\text{proofs of } s\} \to \{3\text{-colorings of } s\}$ for statements $s$. If $G(\text{FLT})$ were a finite graph, this would mean we can check whether it holds true through a finite search, which seems very strange. What am I getting wrong?  

---

## 1 answers

### Answer by username_2 on 2022-08-02. Score: 2 | Accepted answer

The $NP$-problem here is not the problem of finding y,z,n, but rather the following problem:
"Given a mathematical statement $A$ that can be encoded in $n$ bits, does there exist a proof of $A$ in Peano arithmetic that can be encoded in $p(n)$ bits?" where $p$ is some arbitrary fixed polynomial and the particular encoding is chosen in advance.

This problem is clearly an $NP$-problem, since it is possible to design a polynomial-time Turing machine that takes as an input $A$ and a candidate proof $P$, and says accepts iff $P$ is a valid proof of $A$. Therefore, there is a way to map every statement $A$ into a graph $G(A)$ that is $3$-colorable iff $A$ has a proof of length at most $p(n)$.


---

