tag:blogger.com,1999:blog-3722233.post8658886384920717972..comments2024-05-26T22:10:45.398-05:00Comments on Computational Complexity: Quantifiers: To Parenthesize or not to Parenthesize? Matrix of Formula: To Bracket or not to Bracket? Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger7125tag:blogger.com,1999:blog-3722233.post-60006123131012234312023-06-06T18:51:17.026-05:002023-06-06T18:51:17.026-05:00I think the use of the word "such that" ...I think the use of the word "such that" is underrated and that should be used instead of the :'sAnakinnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-14343136452466527472023-06-06T09:43:13.437-05:002023-06-06T09:43:13.437-05:00This comment has been removed by a blog administrator.Evangelos Georgiadisnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-91720074433703753482023-06-06T09:41:44.003-05:002023-06-06T09:41:44.003-05:00We all strive for clean, clear, consistent and min...We all strive for clean, clear, consistent and minimalistic notation that might even be useful in a programmatic context ... so, it's an interesting observation and good question! <br /><br />Two obvious oracles that have given some deeper thought in this direction -- Don Knuth and Leslie Lamport (in particular, see TLA specs).<br /><br />See, also Kolaitis and Vardi in "The Decision Problem for the Probabilities of Higher-Order Properties" on page 11 (no: parens, bracks)<br />[https://www.cs.rice.edu/~vardi/papers/stoc87rj.pdf]<br /><br /><br /> Evangelos Georgiadisnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-70030578067394958222023-06-05T07:52:32.834-05:002023-06-05T07:52:32.834-05:00I have no idea about complexity theory books. I...I have no idea about complexity theory books. I've read quite a few math and logic books (although most of my books are pretty old). I'd do<br /> <br /> \exists x \forall y B(x,y)<br /> <br />That is, no extra punctuation unless it was needed to make things clear.<br /><br />The first paper I wrote, I used some quantifier symbols. A friend pointed out that symbols are sometimes harder to read than are words, so I replaced the quantifier symbols with words.David Marcushttps://www.blogger.com/profile/07084520656051241766noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-26392901934102843592023-06-05T02:54:39.516-05:002023-06-05T02:54:39.516-05:00In a French computational complexity book:
- NP is...In a French computational complexity book:<br />- NP is defined in plain French, so no quantifiers but "il existe" and "pour tout";<br />- PH is defined using oracles, so no quantifier;<br />- a characterization of PH using quantifiers is given, using this time quantifiers with no parens, no brackets.<br /><br />Also, I find uncommon your solution with colons as a separator. It seems more common to either using no separator, or a simple comma.*<br /><br />Finally, I completely agree with what you write: "parenthesis are just so 1979." B.noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-56484702715141377772023-06-05T01:09:36.818-05:002023-06-05T01:09:36.818-05:00I vote for always parenthesize/always bracket. But...I vote for always parenthesize/always bracket. But it's a programming thing (I've seen operator precedence biting people too often), not a theory thing.<br /><br />I'd gues that in proofs (at least in the statement of the thing to be proved), the for alls and there exists appear in language, not notation, e.g. "Given any integers n and m > 0..." and the like.<br /><br />At least that's what statements of theorems look like in the Discrete Math texts I'm looking at.<br />Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-56906246727910681092023-06-05T00:47:45.393-05:002023-06-05T00:47:45.393-05:00Good notation question!
As for the "RARITY of...Good notation question!<br />As for the "RARITY of the use of quantifiers"....<br />I thought there were some quantifiers in Papadimitriou's 1994 book (but not on pages defining NP).<br />Yet another classic "Randomized Algorithms" by Motwani (intriguingly, this book doesn't make it as reference in your book) ... has some quantifiers on page 20 when defining NP, yet served w/o parens.<br /><br /><br />E.G.-1noreply@blogger.com