Complexity Theory Class Notes
1. algorithms
Def: algorithm
Def: turing machine
Example:
Def: space & time of turing machine
1.1. precise algorithms
1.1.1. time complexity criterias
1.1.1.1. average time
Def:
1.1.1.2. worst time
Def:
1.1.1.3. amotized analysis
1.1.1.3.1. aggregate analysis
Def: think of all n operation together
1.1.1.3.2. accounting method
Def:
Note: key is to design cost .
1.1.1.3.3. potential method
Def:
- Note: potential is actually a way of designing accounting method.
1.1.2. algorithm types
1.1.2.1. p
1.1.2.2. pseudo-p algorithm
Def: seudo-P algorithm
Note:
1.2. approximate algorithms
Note: different level of algorithms
Note: different lower bounds
1.2.1. ratio criterias
1.2.1.1. worst-time ratio
Def: worst-time ratio
1.2.1.2. average-time ratio
Def: (expected) average constant ratio
1.2.1.3. asymptotic ratio
Def: asymptotic
Note: difference with 1.3.2 => when the size of instance changes, asymptotic ratio changes
Note: the figure below shows relationship[\(C^*(I), C^A(I)/C^*(I)\)] between two ratios, red is constant r1, blue r2+b/C*I is decreasing(where r2 is the end height, larger b means higher line, to prove an algorithm is efficient we want b to be small, to prove a problem is hard we want it large), so r2 \(\leq\) r1 and r2 represent a more general (excluding special cases like the leftest point) bound of algorithm. To prove r2 is more difficult, such as we have to construct a series of cases to prove that r2 \(\geq\) c,(consider you can't rotate the blue line to the right anymore since bounded by the cases) where in constant ratio we only need one case.
1.2.1.4. competitive ratio
Def: for online algorithm
1.2.2. algorithm types
1.2.2.1. FPTAS & PTAS
Def: FPTAS & PTAS with worst ratio
Note: note that FPTAS is actually a special pseudo-poly when \(\epsilon = 1/MAX\)
Qua: => FPTAS->PTAS
Qua: prove by reduction
1.2.2.2. APTAS
Def: APTAS with asymptotic
1.2.2.3. constant worst ratio
Def: constant ratio with worst ratio
Note: figure of a single instance(note this is not instance level but a single instance)
IMG_2699 Qua: ways to prove lower/upper bounds for Algorithm: find bounds / find difference
Qua: ways to prove no approximation for Problem (equivalent to prove bounds for all algorithms) (GAP-technique)
Note: 1) X \(\geq_p\) Y(some other NPC problems), and separate the domain of X by reduction from Y.
Note: fig, note that everything happens on instance level.
IMG_4787 Qua: ways to prove constant ratio for Problem
Note: 1) X \(\geq_L\) Y(some problem with known ratio)
1.2.2.4. constant competitive ratio
Def: for online algorithm with competitive ratio
Qua: => to prove worst ratio \(\geq\) a for a problem, design a sequence for all algorithms.
Qua: => prove ratio \(\leq\) b for an algorithm, use lower bound.
2. complexity class
Note: classes for desition problems
Note: Fig: classes for optimization problems
Def: size
Example: TSP size
Def: max number
Example: TSP
Example: graph
Def: time complexity
Def: subproblems
sub \(\leq\) general
2.1. class ( for decision problems)
2.1.1. P
Def:
solvable
DTM
2.1.2. NP
Def:
checkable
NDTM
2.1.3. EP
Def:
2.1.4. ZPP
Def:
2.1.5. BPP
Def:
2.1.6. RP
Def:RP
Def: co-RP
2.1.7. NPC
2.1.7.1. NPC
Def: NPC
Qua necc &suff
2.1.7.2. strong NPC
Def: unary NPC (strong NPC)
Qua: => no pseudo
Proof: set a pseudo algorithm A with respect to MAX(I), then it's a P algorithm.
Qua: =>
Qua: prove that max(x) is bounded =>
Note: that the problem being reduced don't need to be strong
Qua: prove by pseudo reduction =>
Note: that using pseudo reduction, the problem has to be strong.
Proof: first prove NP-C, then prove NP-C strong ( max(I2) is bounded)
Note: because it is strong NPC, we can slightly loosen the constraint => from poly to pseudo poly, the second & third conditions are normally less strict than \(max(I_2) \leq p(size(I_2))\)
Qua: with condition => prove no FPTAS
Note: that this requires result to be integers
Proof: the intuition is to design a pseudo to make contradictionm so \(\epsilon\) is intuitive to include size and Max. And to make it optimal, we have to make C* small enough to be the same as CA.
2.1.8. co-NP
Def:
Qua:
Qua:
2.1.9. APX
Def:
Qua:
2.1.10. NPO
- Def:
2.1.11. NPO-C
Def:
2.2. relationship
2.2.1. hard/complete
Def: complete can not be extend to algorithmic problems
2.2.2. equivalence
Def:
2.2.3. reduction
2.2.3.1. turing reduction
- Def:
2.2.3.2. polynomial time reduction
Def:
Note:
2.2.3.3. sudo-p-time reduction
Def: sudo-p-time reduction
Qua: => can be used to prove strong NPC
2.2.3.4. L reduction
Def:
2.2.3.5. PTAS reduction
Def:
