---
tags: Master
---

# COMP3

# Computing
Given a function, or equivalently a set, we say that it is computable (or decidable, or recursive) if and only if a procedure can be described to compute the function’s outcome in a finite number of steps.

(Collatz) However, we have provided a procedure that terminates with the correct answer when the answer is “yes” (the function is not total, in the sense that it doesn’t always provide an answer). We call such set recursively enumerable (or RE, in short).

The diagonal method

# (deterministic) TMs
- multi-tape same as single (constant overhead)
- 2-size alphabet same as any bigger alphabet (constant overhead)

## Universal TMs
(Church-Turing thesis). Turing machines are at least as powerful as every physically realizable model of computation.
The set of decision functions f : N → {0, 1} (or, equivalently, f : Σ∗ → {0, 1}), is uncountable.
Given a finite alphabet Σ, the number of TMs on that alphabet is countable.
There are uncomputable decision functions.
HALT is uncomputable
HALTε is uncomputable
A decision function f : Σ∗ → {0, 1} is recursive if and only if it is both R.E. and co-R.E.
Busy beaver is uncomputable

Let languages L1 and L2 and function f be such that L1 <f L2; then
1. if L2 is decidable and f is computable, then L1 is decidable too;
2. if L1 is undecidable and f is computable, then L2 is undecidable too;
3. lf L1 is undecidable and L2 is decidable, then f is uncomputable.
(Rice’s Theorem). All non-trivial semantic properties of TMs are undecidable.

PCP (Post Correspondance Problem) (stringhe concatenate ripetute) is undecidable

Kolmogorov complexity (livello di compressione) is undecidable (“The smallest positive integer not definable with less than thirteen Englishwords.”)


# P vs NP and Non-det TMs
Non-det TM:
- branches each time it can choose multiple paths and executes them together
- "chooses" the perfect path for acceptance

DTIME(f) = n° step max determ TM è limitato da f
NTIME(f) = .. ........ non-det TM ..

P = DTIME polinomiale
NP = NTIME polinomiale = verifica con certificato in DTIME polinomiale

certificato = informazione utile a verificare che x app a L (che x non app a L nei coNP, co...)
NB: certificato polinomiale rispetto a input

NP hard: at least as hard as all NP (all NP have reduction to this Language)
NP complete: NP hard and NP (the hardest in NP)
reductions are POLINOMIAL (L=>L1 adds polinomial overhead to the equivalent L1 problem)
L complete and L=>L1 (LT ≤p L1) implies L1 complete

L (log space), NL
(Savitch’s theorem). Given a function f(n), NSPACE f(n) ⊆ DSPACE f(n)^2
PSPACE = NPSPACE

# NP complete
- SAT (TM => boolean circuits => SAT)
- 3-SAT
- INDSET: set of vertices of size K that are all disconnected
- CLIQUE: opposite of INDSET: set of vertices of size K that are all connected (complete)
- ILP: Integer Linear Programming (boh)
- VERTEX COVER: vertex subset of size <= k such that every edge is connected to at least one vertex
- 3-VERTEX COLORING (with 3 colors)
- SET COVER: pick exactly k of the given subsets of S, union must be S
- SUBSET SUM: pick elements so that sum=k
- KNAPSACK: max capacity is C and minimum value to achieve is V
- (directed) HAMILTONIAN PATH: find path that touches every vertex exactly once (in directed graph)
- DIRECTED HAMILTONIAN CYCLE: find cycle (closed path) that touches every vertex exactly once
- UNDIRECTED HAMILTONIAN CYCLE
- TRAVELING SALESMAN PROBLEM: given undirected COMPLETE graph, find hamiltonian path of total edge cost <= K
- K-VERTEX COLORING (k colors)
-

# THEOREMS
### theorem 1: k-tape machine emulation in O(T(n)^2)
need c*T(n) steps for each step of the original machine, therefore
c*T(n)*T(n) = O(T(n)^2)

### theorem 2: alphabet to binary emulation in O(T(n))
need extra states to remember what I'm reading and what I'm writing

### Church-Turing thesis

### Decision functions are uncountable

### TMs in sigma star are countable

### There are uncomputable decision functions

### Theorem 3
UC(uc) would give the opposite of UC(uc) (impossible)

### Theorem 4: HALT is uncomputable
Reduce UC to HALT

### Theorem 5: HALTe is uncomputable
Machine that writes its own input, then starts computing
We reduced HALT(s,t) to HALTe(s) => impossibru

### Theorem 6

### Theorem 7

### Busy beaver

### S(n) is uncomputable
Could run S(n) steps to check HALT

### Theorem 9: Busy beaver outgrows everything

### Theorem 10: Reductions

### Using HALT to check mathematical problems

### RICE's theorem

### PCP problem

### Kolmogorov complexity

## P vs NP
### Polinomial time

### CNF

### NP definition 1

### NP definition 2

### K-sat <= SAT

### SAT <= 3-SAT

### CLIQUE equivalent to INDSET

### 3-sat <= INDSET

## NP hard and NP complete

### SAT is NP hard (therefore NP complete)

### NP complete reductions