Here on the page 354 Arora and Barak write below the shaded area

"but in fact $f(\phi)$ $\notin SAT$"

and not

"but in fact $f(\phi) \in SAT$"

While in the last line of the shaded area they write

$Pr[f(\phi)\in SAT]=0$

Shouldn't there be in that last line also not:

$Pr[f(\phi)\notin SAT]=0$


  • 1
    $\begingroup$ You might have found a typo. If the text makes sense with your correction, but doesn't make sense without your correction, then it's a typo. They happen. Humans are not infallible. $\endgroup$ – Yuval Filmus Jun 30 '18 at 14:08
  • $\begingroup$ The thing is that I'm not sure that it is a typo and how it should be corrected.In the corollary 17.20 on page 355 4th row in that corollary there is something similar: $$A(\phi)\in \oplus \text{SAT}$$ I do not believe that they would make the same typo 2 times in a row. Can someone reliable please have a look at these two lines of the book and let me know what is right and what is wrong? $\endgroup$ – user2925716 Jun 30 '18 at 16:04
  • 1
    $\begingroup$ Part of the skill involved in reading papers and monographs (and, in this case, textbooks) is acknowledging the existence of mistakes, identifying them, and, when possible, correcting them. $\endgroup$ – Yuval Filmus Jun 30 '18 at 16:31
  • $\begingroup$ Of course. But can someone tell me how these 2 lines (4th line of corollary 17.20 and last line of the shadowed area on page 354) should look like. Actually I do not know what is correct and what is my incapability. $\endgroup$ – user2925716 Jun 30 '18 at 16:34
  • 1
    $\begingroup$ Your problem only makes sense for people in possession of a copy of the Arora–Barak textbook. Perhaps you could provide a self-contained version of your doubt? $\endgroup$ – Yuval Filmus Jun 30 '18 at 17:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.