01 Abstract Problem

In computer science we consider many data structure, for instance natural numbers, graphs, strings, etc.
For the purpose of computation we shall identify these data structures as binary strings, i.e. elements of $\{0,1{\}}^{\star }$.

• A natural number is identified with its binary representation.
• A subset $X\subseteq \{0,\cdots ,n-1\}$ is identified with a $n$-bit binary string $X_0,\cdots ,X_{n-1}$, with $X_i=1$ just if $i\in X$.
• A (directed) graph is identified with its set of edges.
• A string over a finite alphabet $\Sigma$ is identified with a binary string by fixing some prefix-free coding of $\Sigma$ within $\{0,1{\}}^{\star }$.

Note

For $x\in \{0,1{\}}^{\star }$ we shall $|x|$ for its length as a binary string, and extend this notation to other data structures too, cf. above.

Examples

Natural Numbers

$$\begin{array}{ccc}\text{Number}& \text{Binary representation}& \text{Size}\\ 0& 0& 1\\ 1& 1& 1\\ 2& 10& 2\\ 3& 11& 2\\ 4& 100& 3\\ 5& 101& 3\\ ⋮& ⋮& ⋮\end{array}$$

For a positive integer $n$, the length of its binary representation is

$$|n|=\lfloor {\log }_{2}n\rfloor +1(n\ge 1)$$

Sets

$$\begin{array}{lcc}X\subseteq \{0,1,2,3\}& & \\ \text{Set}& ⟶& \text{Binary encoding}\\ \{0\}& ⟶& 1000\\ \{1,3\}& ⟶& 0101\\ \varnothing & ⟶& 0000\\ \{0,1,2,3\}& ⟶& 1111\end{array}$$

Problems

Since we represent all data as binary strings, we may define:

Definition

A language or predicate is just a subset of $\{0,1{\}}^{\star }=$ binary strings

We also sometimes speak of problem, whose solutions are identified with the corresponding language/predicate.
When speaking of data other than binary strings, we may speak of an instance of a problem to mean an instance of that data, e.g, a graph or a natural number.

The Satisfiability Problem

Fix a set of propositional variables $\{p_0,p_1,p_2,\cdots \}=\text{Prop}$
Formulas: $A,B,\cdots :=p_i|\neg A|A\wedge B|A\vee B$
Assignment: $\alpha :\text{Prop}\to \{0,1\}$
Eval:

• $\alpha (\neg A)=1-\alpha (A)$
• $\alpha (A\vee B)=\max (\alpha (A),\alpha (B))$
• $\alpha (A\wedge B)=\min (\alpha (A),\alpha (B))$

SAT is the set of formulas $A$ S.T $\exists \alpha :\alpha (A)=1$.