44 A first non-uniform class

We identify Boolean functions $f:\{0,1{\}}^n\to \{0,1\}$ with languages $\subseteq \{0,1{\}}^n$ in the expected way.

We say that a language $L\subseteq \{0,1{\}}^{\star }$ is computed by a family $\{A_n{\}}_{n=1}^{\infty }$ of CNFs if, for each $n\in \mathbb{N}$, $A_n$ is a CNF computing $L\cap \{0,1{\}}^n$.

We may now define our first ‘non-uniform class’:

Definition

The size of a CNF $A$, written $|A|$, is its number of literal occurrences. ${\mathbf{CNF}}^{poly}$ is the class of languages computed by a polynomial size CNFs.

Example $<2$ out of $n$

The functions ${\mathrm{ATMOST}}_1^n:\{0,1{\}}^n\to \{0,1\}$ are defined by:

$${\mathrm{ATMOST}}_1^n(x_1,\cdots ,x_n)=1⟺<2\text{ of }{x}_1,\cdots ,x_n\text{ are }1$$

The ${\mathrm{ATMOST}}_1^n$ functions are computed by the following CNFs:

$$\underset{i=1}{\overset{n-1}{\bigwedge }}\underset{j=i+1}{\overset{n}{\bigwedge }}(\neg x_i\vee \neg x_j)$$

Note that $|{\mathrm{ATMOST}}_1^n(\overrightarrow{x})|=n(n-1)$. Therefore ${\mathrm{ATMOST}}_1^n\in {\mathbf{CNF}}^{poly}$