Timeline for Is quadratic nonresiduosity in $\textbf{NP}$?
Current License: CC BY-SA 4.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 29, 2023 at 8:56 | comment | added | EGME | In communication with B. Barak, he points out that this is a mistake in their book (example 8.9). Both QR and QNR are in NP. A nice proof of this appears in Cai and Threlfall’s paper (you can google it to find the non-paywall version): sciencedirect.com/science/article/pii/S0020019004001991 | |
| Mar 6, 2023 at 11:16 | comment | added | user93353 | I am currently reading Goldwasser's paper on Zero Knowledge proofs (GMR85) & there it's clearly said that both QR & QNR are in NP & I can't find where exactly Borak-Arora says it's not in NP - can you tell me the page/chapter number? | |
| May 26, 2021 at 1:04 | comment | added | Johnny | I just sent an email to an account that the authors maintain for improvements to the book. I'll provide an update here if they ever respond. | |
| May 26, 2021 at 0:11 | history | edited | D.W.♦ | CC BY-SA 4.0 |
added 112 characters in body
|
| May 26, 2021 at 0:10 | comment | added | D.W.♦ | @kotu, got it, thank you. I'm confused, too. I hope someone here who knows more computational complexity than I will be able to help us clear this up. | |
| May 25, 2021 at 23:10 | comment | added | Johnny | I appreciate you taking the time to answer regardless. In the "chapter notes and history" section of chapter 7 in my book they refer to the paper which proved PRIMES is in P, so now I'm just more confused =P | |
| May 25, 2021 at 23:07 | history | edited | D.W.♦ | CC BY-SA 4.0 |
added 515 characters in body
|
| May 25, 2021 at 23:03 | comment | added | D.W.♦ | @kotu, I don't know. Arora and Barak know way more than me, so if my impression is contrary to them, I'm inclined to think it's more likely that I've misunderstood something than that they got something wrong. Depending on how old your copy of the book is, perhaps it was written before the proof that PRIMES is in P, in which case everything they write makes sense; my answer basically argues that the problem is in NP, and relies upon the fact that PRIMES is in P: the witness is a prime $p$ that divides $n$, and the verifier must verify that $p$ is a prime. | |
| May 25, 2021 at 22:49 | comment | added | Johnny | So Arora-Barak is wrong? | |
| May 25, 2021 at 22:44 | history | answered | D.W.♦ | CC BY-SA 4.0 |