0

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"?

Burak
  • 161
  • 2
  • 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 Nov 08 '19 at 13:27
  • 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 Nov 08 '19 at 13:42
  • 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 Nov 08 '19 at 13:45
  • 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 Nov 08 '19 at 17:26
  • @Burak, does my comment above yours answer that question? – usul Nov 08 '19 at 20:25
  • 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 Nov 09 '19 at 07:07
  • @usul Yes, your answer and link solved my question. Thanks! – Burak Nov 10 '19 at 10:19

0 Answers0