0
$\begingroup$

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

Improve this question
$\endgroup$
7
  • $\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$
    – Emil Jeřábek
    Commented 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
    Commented 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
    Commented 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
    Commented Nov 8, 2019 at 17:26
  • $\begingroup$ @Burak, does my comment above yours answer that question? $\endgroup$
    – usul
    Commented Nov 8, 2019 at 20:25

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.