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

  • $\begingroup$ 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. $\endgroup$ Nov 8, 2019 at 13:27
  • $\begingroup$ 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. $\endgroup$
    – usul
    Nov 8, 2019 at 13:42
  • $\begingroup$ 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 cstheory.stackexchange.com/questions/17456/… $\endgroup$
    – usul
    Nov 8, 2019 at 13:45
  • $\begingroup$ 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. $\endgroup$
    – Burak
    Nov 8, 2019 at 17:26
  • $\begingroup$ @Burak, does my comment above yours answer that question? $\endgroup$
    – usul
    Nov 8, 2019 at 20:25


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.