# Is it possible to create an arbitrary $\textsf{NP}$-complete statement of chosen size $n$ and witness in polynomial time?

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

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