Timeline for Is NP in NP/Poly?
Current License: CC BY-SA 4.0
30 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 25, 2020 at 15:16 | history | edited | DeeDee | CC BY-SA 4.0 |
deleted 1 character in body
|
| Nov 25, 2020 at 15:13 | comment | added | DeeDee | @YuvalFilmus ok, i get it from the view of your translation--from the angle before I was just worried about a single circuit being able to handle some extreme case where |y|+𝑝(|y|)=|x|+𝑝(|x|)=|z|+𝑝(|z|)=|v|+𝑝(|v|)=... an exponential number of valid certificate word combos fall on the same length--and those p(v), p(y)... are descriptions of solution paths--now a single circuit needs to be able to simulate an exponential number of solution paths p(y) on on all those words y they are solution paths for, and such a circuit still needs to be max poly size--this seemed impossible to me. | |
| Nov 25, 2020 at 15:04 | vote | accept | DeeDee | ||
| Nov 25, 2020 at 14:59 | answer | added | Yuval Filmus | timeline score: 3 | |
| Nov 25, 2020 at 14:51 | comment | added | Yuval Filmus | Do you know how to translate a Turing machine to a circuit? This is essentially Cook's theorem. | |
| Nov 25, 2020 at 14:50 | comment | added | Yuval Filmus | It doesn't matter what the certificate $y$ is. We don't care. All we need to know is that there is a polytime deterministic Turing machines that can compute $C(x,y)$. | |
| Nov 25, 2020 at 14:49 | comment | added | Yuval Filmus | I'm really not sure how to carry this point across more clearly: you have a sequence of circuits $c_1,c_2,\ldots$, where $c_n$ gets two inputs: $x$ of size $n$, and $y$ of size $p(n)$, where $p$ is some polynomially bounded function. | |
| Nov 25, 2020 at 14:49 | comment | added | DeeDee | @YuvalFilmus sometimes the certificate y for a word x is itself a description of the solution path -- in the case for such certificates you verify the word x by essentially simulating y on (x) -- if an exponential number of these line up and fall on one circuit -- dont see how it can be guaranteed to only be poly size when it needs to handle all these diff simulations | |
| Nov 25, 2020 at 14:48 | comment | added | Yuval Filmus | There could be multiple combinations having the same length, but it makes absolutely no difference, since you have a different circuit for each $|x|$. The circuit knows $|x|$. | |
| Nov 25, 2020 at 14:44 | comment | added | DeeDee | @YuvalFilmus the circuit accepts arguments of size |certificate| + |word| -- there could be multiple different |certificate| + |word| combos that have the same length--then a single circuit would need to simulate multiple polytime Turing machine paths -- and you could have up to 2^n word, certificate combinations line up this way -- if this happens then a single poly size circuit needs to carry the burden of simulating an exponential number of different poly time machines (certificates) on all the different words those solution paths are certificates for. | |
| Nov 25, 2020 at 14:40 | comment | added | Yuval Filmus | I really don't follow. The circuit gets $x$ and $y$, and simulates the deterministic polytime Turing machine on $x$ and $y$. You can do this with a polynomial size circuit. | |
| Nov 25, 2020 at 14:38 | comment | added | DeeDee | @YuvalFilmus I'm referring to Dimitry's comment "the input layer of the circuit will have size |𝑥|+𝑝(|𝑥|)" if you have multiple certificate, word combinations lining up all with same length -- then the same circuit would need to handle all of them (because as you said one circuit for each input size --there could be a case where an exponential number of these line up and in this case you would still need to guarantee a poly size circuit exists that can handle this unfortunate coincidence | |
| Nov 25, 2020 at 14:35 | comment | added | Yuval Filmus | No. You have a difference circuit for each $|x|$. It doesn't matter if this sort of coincidence happens. | |
| Nov 25, 2020 at 14:34 | comment | added | DeeDee | @YuvalFilmus right, but could there not be a situation where certificate + word and anther certificate + word combination happen to fall on the same length and therefor the same circuit needs to handle both of these -- and there could be even more (an exponential number could line up this way). | |
| Nov 25, 2020 at 14:32 | comment | added | Yuval Filmus | No. You have a different circuit for each $|x|$. | |
| Nov 25, 2020 at 14:31 | comment | added | DeeDee | @YuvalFilmus in the case where the certificate is a description of a solution path and there are two |y|+𝑝(|y|) if |y|+𝑝(|y|)=|𝑥|+𝑝(|𝑥|) or more arguments of same length for the circuit--then a single circuit would need to walk multiple (possibly exponential) number of solution paths to verify a bunch of w's whose w + c all happen to line up with that length, could there not be a case like this? | |
| Nov 25, 2020 at 8:32 | comment | added | Yuval Filmus | By padding witnesses, you can assume that their size only depends on the input size. | |
| Nov 25, 2020 at 8:31 | comment | added | Yuval Filmus | The verifier $V$ is a deterministic Turing machine. There is only one computation branch. | |
| Nov 25, 2020 at 2:49 | history | edited | DeeDee | CC BY-SA 4.0 |
edited body
|
| Nov 25, 2020 at 2:38 | comment | added | DeeDee | @Dmitry cleaned it up a bit--thank you--addressing your comment in relation to the question: does that mean there is a poly size circuit for every length of word +certificate pair? If so, some of those circuits might need to accept |𝑥|+𝑝(|𝑥|) as well as another |y|+𝑝(|y|) if |y|+𝑝(|y|)=|𝑥|+𝑝(|𝑥|). Cases like this seem like they could present a problem, no? How can you predict when this is going to happen? | |
| Nov 25, 2020 at 1:15 | history | edited | DeeDee | CC BY-SA 4.0 |
deleted 382 characters in body
|
| Nov 24, 2020 at 22:33 | history | edited | DeeDee | CC BY-SA 4.0 |
added 4 characters in body
|
| Nov 24, 2020 at 22:19 | comment | added | user114966 |
The last paragraph is hard to understand. Please try to reformat it (at least split this into bullet list: one item per issue). there are an infinte number of c's that are poly|w| that are potential certificates for w's of length b--how can a single circuit ... accept on all the different certificates for the w's - you don't care about all of them. It suffices to know that there exists a certificate with size polynomial of input size. For each $x$. there exists a certificate of size $p(|x|)$: the input layer of the circuit will have size $|x| + p(|x|)$. This way, it'll include some cert.
|
|
| Nov 24, 2020 at 21:49 | history | edited | DeeDee | CC BY-SA 4.0 |
added 4 characters in body
|
| Nov 24, 2020 at 21:12 | history | edited | DeeDee | CC BY-SA 4.0 |
deleted 4 characters in body
|
| Nov 24, 2020 at 19:23 | history | edited | DeeDee | CC BY-SA 4.0 |
deleted 10 characters in body
|
| Nov 24, 2020 at 19:16 | history | edited | DeeDee | CC BY-SA 4.0 |
added 443 characters in body
|
| Nov 24, 2020 at 19:09 | history | edited | DeeDee | CC BY-SA 4.0 |
added 443 characters in body
|
| Nov 24, 2020 at 19:00 | history | edited | DeeDee | CC BY-SA 4.0 |
added 443 characters in body
|
| Nov 24, 2020 at 18:54 | history | asked | DeeDee | CC BY-SA 4.0 |