For the book

**Computational Intractability: A Guide to Algorithmic Lower Bounds**

by Demaine-Gasarch-Hajiaghayi

(See here for a link to a first draft.)

we had to make some choices about which notation to use. One of the least important ones was the following:

When defining NP, and in a few other places should we use:

(\exists y)(\forall y)[B(x,y)]

or

\exists x : \forall y : B(x,y)

or

something else.

We ended up doing it the second way. But I wondered, which, if either, is standard. So I looked in many math and theoretical CS books looking for places they used quantifiers. Here is what I found

a) Most papers and books really don't use quantifiers at all! This surprised me.

b) When quantifiers are used, they are used in definitions, not theorems.

c) One exception is in logic when they deal with formulas as objects onto themselves. For example, the inductive definition of a formula will have a step:

If f(x_1,...,x_n) is a formula then (\exists x_i)[f(x_1,...,x_n)] is a formula.

d) Here is a list of the few places I saw quantifiers used and if they used parenthesis or not. I say if it has parenthesis (abbreviated Parens) or not, and if the matrix of the formula is in square brackets, no brackets, or something ese.

*Cook's classic paper . *Page 154 Parens, no Brackets (1971)

*Stockmeyer's paper where he defines PH*. Page 6 Parens and Brackets (1976)

*Computers and Intractability* by Garey & Johnson. Page 164. Parens and Brackets (1979)

*Morass-like construction of aleph_2 trees in L* by Devlin. Page 2 Parens and matrix in Parens (1979)

*Descriptive Complexity by Immerman.* Page 38 Parens no Brackets (1999)

*Bounded Queries in Recursion Theory *by Gasarch and Martin. Parens and Brackets Throughout the book. (1999)

*Complexity Theory from Godel to Feynman* by Rudich. No Parens, No Brackets in Def of PH. (2003)

Parameterized Complexity Theory by Flum & Grohe. Page 81 no Parens and no Brackets.

*Computational Complexity: A Modern Approach *by Arora & Barak. Page 40. No Parens No Brackets.(2007)

Computational Complexity: A Conceptual Prospective by Goldreich. Page 114 no parents, no brackets (2008)

*On Quantifer Rank Equivalence between linear orders by Siders. *On page 417 they use quantifiers to state a theorem, which is unusual. Parens no brackets.

*Presburger arithmetic, Rational Generating Functions, and quasi polynomials* by Woods. Parens no Brackets. (2012)

Who witness's the Witness by Abel et al. On Page 69 (which the pointer takes you to) No Parens, no brackets. Colons between quantifiers (2018).

e) What to make of all this?

First off- the RARITY of the use of quantifiers really surprised me. The only place I saw them used a lot was my book, co-authored with Georgie Martin, *Bounded Queries in Recursion Theory. *Perhaps it would have sold better if I didn't use so many quantifiers. Oh well.

Second off- Later works don't use parens and brackets. This is most clear if you just look at Complexity Theory Books

Garey & Johnson - 1979- parens and brackets

Flun & Grohe- 1998- no parens and no brackts

Immerman- 1999 - parens but no brackets (this is the one exception)

Arora & Barack- 2007 no parens and no brackets

Goldreich-2008- no parens and no brackets

If you have a complexity theory book around that is not on this list, look up the definition of NP and the definition of the Poly Hierarchy and see (a) if they use parens around the quantifiers, and (b) if they use square brackets or no brackets of something else. Please leave a comment about it so I test the conjecture that parenthesis are just so 1979.