<p>This questions came in my mind as I was reading the concept of hidden-bits of Feige, Lapidot and Shamir in "<em>Multiple non-interactive zero knowledge proofs based on a single random string</em>". There is one part about the construction of zero knowledge proofs of Hamiltonicity of directed graphs.</p>

<blockquote>
  <p>Let <span class="math-container">$H$</span> be a randomly chosen Hamiltonian cycle on <span class="math-container">$n$</span> nodes. ... Assume now that P wants to prove <span class="math-container">$V$</span> the Hamiltonicity of some graph with <span class="math-container">$n$</span> nodes. ... Let <span class="math-container">$\pi$</span> be a permutation that maps H onto the Hamiltonian cycle of <span class="math-container">$G$</span>.</p>
</blockquote>

<p>I know that <span class="math-container">$\textsf{NP}$</span> is the class of problems, where its membership can be verified in polynomial-time. However, the sentence that <span class="math-container">$H$</span> is a randomly chosen Hamiltonian cycle on <span class="math-container">$n$</span> nodes looks very "easy". Either the computation of such a graph is easy, therefore it is in polynomial time or their idea was to choose some familiar instance of it.</p>

<p>Since, Hamiltonicity is NP-complete and assume it is easy to compute an arbritary instance of size <span class="math-container">$n$</span> with an associated witness, it is possible to create for every <span class="math-container">$\textsf{NP}$</span>-complete problem an example instance in polynomial-time?</p>

<p>Another question which follows from this: If we rely on such a generated instances <span class="math-container">$s$</span> of a problem to prove some other statement, wouldn't the soundness of the proof be violated if <span class="math-container">$s$</span> is choosen "bad"?</p>

CC BY-SA 4.0
2019-11-08T13:27:46.850Z
I don’t understand the question. The quote explicitly tells you that $H$ is *not* constructed by any deterministic polynomial-time algorithm, but that it is drawn from a random distribution (presumably the uniform distribution on all $n$-cycles, which is easy to sample). This is essential for the correctness of protocol.
Emil Jeřábek
CC BY-SA 4.0
2019-11-08T13:42:52.483Z
I'm guessing that the authors mean to take any permutation of the vertices, whereas you are interpreting the quote to mean find a random hamiltonian cycle of some given graph.
usul
CC BY-SA 4.0
2019-11-08T13:45:59.860Z
In general it's easy to generate instances and witnesses for NP-complete problems, e.g. we generate the complete graph and any permutation, that's a Hamiltonian cycle. A good question is whether we can generate instances that are hard to solve, which requires some assumptions similar to cryptography ... see related https://cstheory.stackexchange.com/questions/17456/the-examiners-problem-uniform-generation-of-sat-decision-instances-answers
usul
CC BY-SA 4.0
2019-11-08T17:26:43.080Z
My question is actually independend from the quote: For an NP language $\textrm{L}$, can we create a "random" word $x$ with size $|x| = n$ and witness $w$ in polynomial time? The question came in my mind as I was reading the part of the paper, where I was unsure, from where Hamiltonian cycle $H$ comes from.
Burak
CC BY-SA 4.0
2019-11-08T20:25:52.760Z
@Burak, does my comment above yours answer that question?
usul
CC BY-SA 4.0
2019-11-09T07:07:45.563Z
I read the problem as "for every  Complete language L, is there a TM that on input $n$ outputs a size-$n$ member of $L$ in time $\textrm{poly}(n)$?". The answer is no, because some NP Complete languages will not have any size-$n$ members (e.g. SAT restricted to even sized inputs is still NP Complete). But for size $\geq n$, the problem seems a bit more interesting.
Yonatan N
CC BY-SA 4.0
2019-11-10T10:19:14.117Z
@usul Yes, your answer and link solved my question. Thanks!
Burak
<zero-knowledge>
Is it possible to create an arbitrary $\textsf{NP}$-complete statement of chosen size $n$ and witness in polynomial time?
Burak
# Is it possible to create an arbitrary $\textsf{NP}$-complete statement of chosen size $n$ and witness in polynomial time?

(Asked by: username_0 on 2019-11-08)

This questions came in my mind as I was reading the concept of hidden-bits of Feige, Lapidot and Shamir in "*Multiple non-interactive zero knowledge proofs based on a single random string*". There is one part about the construction of zero knowledge proofs of Hamiltonicity of directed graphs.

> Let $H$ be a randomly chosen Hamiltonian cycle on $n$ nodes. ... Assume now that P wants to prove $V$ the Hamiltonicity of some graph with $n$ nodes. ... Let $\pi$ be a permutation that maps H onto the Hamiltonian cycle of $G$.

I know that $\textsf{NP}$ is the class of problems, where its membership can be verified in polynomial-time. However, the sentence that $H$ is a randomly chosen Hamiltonian cycle on $n$ nodes looks very "easy". Either the computation of such a graph is easy, therefore it is in polynomial time or their idea was to choose some familiar instance of it.

Since, Hamiltonicity is NP-complete and assume it is easy to compute an arbritary instance of size $n$ with an associated witness, it is possible to create for every $\textsf{NP}$-complete problem an example instance in polynomial-time?

Another question which follows from this: If we rely on such a generated instances $s$ of a problem to prove some other statement, wouldn't the soundness of the proof be violated if $s$ is choosen "bad"?

**Tags:** zero-knowledge
> **Comments:**
> **username_1**: I don’t understand the question. The quote explicitly tells you that $H$ is *not* constructed by any deterministic polynomial-time algorithm, but that it is drawn from a random distribution (presumably the uniform distribution on all $n$-cycles, which is easy to sample). This is essential for the correctness of protocol.  
> **username_2**: I'm guessing that the authors mean to take any permutation of the vertices, whereas you are interpreting the quote to mean find a random hamiltonian cycle of some given graph.  
> **username_2**: In general it's easy to generate instances and witnesses for NP-complete problems, e.g. we generate the complete graph and any permutation, that's a Hamiltonian cycle. A good question is whether we can generate instances that are hard to solve, which requires some assumptions similar to cryptography ... see related https://cstheory.stackexchange.com/questions/17456/the-examiners-problem-uniform-generation-of-sat-decision-instances-answers  
> **username_0**: My question is actually independend from the quote: For an NP language $\textrm{L}$, can we create a "random" word $x$ with size $|x| = n$ and witness $w$ in polynomial time? The question came in my mind as I was reading the part of the paper, where I was unsure, from where Hamiltonian cycle $H$ comes from.  
> **username_2**: @Burak, does my comment above yours answer that question?  
> **username_3**: I read the problem as "for every  Complete language L, is there a TM that on input $n$ outputs a size-$n$ member of $L$ in time $\textrm{poly}(n)$?". The answer is no, because some NP Complete languages will not have any size-$n$ members (e.g. SAT restricted to even sized inputs is still NP Complete). But for size $\geq n$, the problem seems a bit more interesting.  
> **username_0**: @usul Yes, your answer and link solved my question. Thanks!  

---

## 0 answers

