Timeline for Is it possible to create an arbitrary $\textsf{NP}$-complete statement of chosen size $n$ and witness in polynomial time?
Current License: CC BY-SA 4.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 10, 2019 at 10:19 | comment | added | Burak | @usul Yes, your answer and link solved my question. Thanks! | |
| Nov 9, 2019 at 7:07 | comment | added | Yonatan N | 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. | |
| Nov 8, 2019 at 20:25 | comment | added | usul | @Burak, does my comment above yours answer that question? | |
| Nov 8, 2019 at 17:26 | comment | added | Burak | 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 13:45 | comment | added | usul | 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/… | |
| Nov 8, 2019 at 13:42 | comment | added | usul | 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. | |
| Nov 8, 2019 at 13:27 | comment | added | Emil Jeřábek | 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 12:03 | history | asked | Burak | CC BY-SA 4.0 |