10 History of Computing

1950s and 1960s

People began to look at general ways to solve a problem, rather than solving given instance!
- Instance of SAT : Is $(A \lor \neg B) \land (\neg A) \land (B \lor Z \lor \neg X)$ satisfiable?
- How (fast) can we check in general if a CNF-SAT formula is satisfiable ?
Many of the known problems had polynomial running time
- Actually even $n^{4}$ or smaller
Claim Any exponential (ultimately) beats any polynomial
- $1.0000000000 1^{n} > n^{1.00000000001}$ if $n$ is large enough
- Take $lo g$ on both sides!
Differentiate between finite and efficient
Polynomial time became accepted as standard of efficiency
- Closed under addition, multiplication and composition
- $P$ : The class of problems solvable in polynomial time (in size of input).

But still many problems no one knew how to solve in polynomial time!
CNF satisfiability (SAT)
- Say we have $N$ variables and $M$ clauses.
- No algorithm was known to solve $(N + M)^{O (1)}$ time.
- Brute force does $2^{N}$ truth assignments, and checks in $O (N)$ time if each of the $M$ clauses is satisfied.
- So, total running time is $O (2^{N} \cdot N \cdot M)$
- Note that the input size if $N + M$
Can we design a polynomial time algorithm for SAT ?
Or show that such an algorithm cannot exist ?
$NP$ : class of problems where we can verify a potential solution in polynomial time.