Algorithms Tradeoff: Execution speed vs. solution quality Solution fast approximate Short & sweet Quick & dirty slow Speed exact Slowly but surely Too little, too late Computational Complexity Problem: Avoid getting trapped in local minima Global optimum Approximation Algorithms Idea: Some intractable problems can be efficiently approximated within close to optimal! Fast: Simple heuristics (e.g., greed) Provably-good approximations Slower: Branch-and-bound approaches Integer Linear Programming relaxation Approximation Algorithms Wishful: Simulated annealing Genetic algorithms Minimum Vertex Cover Minumum vertex cover problem: Given a graph, find a minimum set of vertices such that each edge is incident to at least one vertex of these vertices. Example:

Input graph Heuristic solution Optimal solution Applications: bioinformtics, communications, civil engineering, electrical engineering, etc. One of Karps original NP-complete problems Minimum Vertex Cover Examples Approximate Vertex Cover Theorem: The minimum vertex cover problem is NPcomplete (even in planar graphs of max degree 3). Theorem: The minimum vertex cover problem can be solved exactly within exponential time nO(1)2O(n). Theorem: The minimum vertex cover problem can not be approximated within 1.36*OPT unless P=NP.OPT unless P=NP. Theorem: The minimum vertex cover problem can be approximated (in linear time) within 2*OPT unless P=NP.OPT. Idea: pick an edge, add its endpoints, and repeat. Approximate Vertex Cover Algorithm: Linear time 2*OPT unless P=NP.OPT approximation for the minimum vertex cover problem: n ! o C i t a V Pick random edge (x,y) m or i x f Add {x,y} to the heuristic solution o r n p w p Eliminate x and y from graph o ts a kn Repeat until graph is empty Be nd u o

b x y Idea: one of {x,y} must be in any optimal solution. Heuristic solution is no worse than 2*OPT unless P=NP.OPT. Maximum Cut Maximum cut problem: Given a graph, find a partition of the vertices maximizing the # of crossing edges. Example: cut size = 2 cut size = 4 cut size = 5 A B A E C D Input graph A B E D C Heuristic solution B E D C Optimal solution Applications: VLSI circuit design, statistical physics,

communication networks. One of Karps original NP-complete problems. Maximum Cut Theorem [Karp, 1972]: The minimum vertex cover problem is NP-complete. Theorem: The maximum cut problem can be solved in polynomial time for planar graphs. Theorem: The maximum cut problem can not be approximated within 17/16*OPT unless P=NP.OPT unless P=NP. =1.0625*OPT unless P=NP.OPT Theorem: The maximum cut problem can be approximated in polynomial time within 2*OPT unless P=NP.OPT. Theorem: The maximum cut problem can be approximated in polynomial time within 1.14*OPT unless P=NP.OPT. Maximum Cut Algorithm: 2*OPT unless P=NP.OPT approximation for maximum cut: Start with an arbitrary node partition If moving an arbitrary node across the partition will improve the cut, then do so Repeat until no further improvement is possible cut size = 2 cut size = 3 A A B E C D Input graph C cut size = 5 A B B

E E D Heuristic solution D C Optimal solution Idea: final cut must contain at least half of all edges. Heuristic solution is no worse than 2*OPT unless P=NP.OPT. Approximate Traveling Salesperson Traveling salesperson problem: given a pointset, find shortest tour that visits every point exactly once. 2*OPT unless P=NP.OPT metric TSP heuristic: Compute MST T = Traverse MST S = shortcut tour Output S Analysis: S < T = 2*OPT unless P=NP.MST < 2*OPT unless P=NP. OPT TSP triangle inequality! T covers minimum spanning tree twice TSP minus an edge is a spanning tree Non-Approximability NP transformations typically do not preserve the approximability of the problem! Some NP-complete problems can be approximated arbitrarily close to optimal in polynomial time. Theorem: Geometric TSP can be approximated in polynomial time within (1+)*OPT unless P=NP.OPT for any >0. Other NP-complete problems can not be approximated within any constant in polynomial time (unless P=NP). Theorem: General TSP can not be approximated

efficiently within K*OPT unless P=NP.OPT for any K>0 (unless P=NP). Graph Isomorphism Definition: two graphs G1=(V1,E1) and G2=(V2,E2) are isomorphic iff bijection :V1V2 such that vi,vjV1 (vi,vj)E1 ((vi),(vj))E2 Isomorphism edge-preserving vertex permutation Problem: are two given graphs isomorphic? Note: Graph isomorphism NP, but not known to be in P Graph Isomorphism Zero-Knowledge Proofs Idea: proving graph isomorphism without disclosing it! Premise: Everyone knows G1 and G2 but not must remain secret! Create random G G1 G ng ti Verifier asks for or Broadcast or Verifier checks GG1 or GG2 Repeat k times Probability of cheating: 2-k

G2 Note: is () Broadcast G G1 p A o r p m i x a p a o o r ! f Zero-Knowledge Proofs Idea: prove graph 3-colorable without disclosing how! Premise: Everyone knows G1 but not its 3-coloring which must remain secret! Create random G2 G1 Note: 3-coloring '(G2) is ((G1)) Broadcast G2 Verifier asks for or ' Broadcast or '

Verifier checks G1G2 or '(G2) Repeat k times Probability of cheating: 2-k G2 ' ! f o o r G1 p e v i t c a r e t In Zero-Knowledge Caveats Requires a good random number generator Should not use the same graph twice Graphs must be large and complex enough Applications: Identification friend-or-foe (IFF) Cryptography Business transactions Zero-Knowledge Proofs Idea: prove that a Boolean formula P is satisfiable without disclosing a satisfying assignment! Premise: Everyone knows P but not its secret satisfying assignment V ! P = (x+y+z)(x'+y'+z)(x'+y+z')

G= In te P is satisfiable iff G is 3-colorable P is satisfiable with probability 1-2-k rac tiv e Publically broadcast and G Use zero-knowledge protocol to show that G is 3-colorable pr oo f! Convert P into a graph 3-colorability instance G =(P) Interactive Proof Systems Prover has unbounded power and may be malicious Verifier is honest and has limited power Completeness: If a statement is true, an honest verifier will be convinced (with high prob) by an honest prover. Soundness: If a statement is false, even an omnipotent malicious prover can not convince an honest verifier that the statement is true (except with a very low probability). The induced complexity class depends on the verifiers abilities and computational resources: Theorem: For a deterministic P-time verifier, class is NP. Def: For a probabilistic P-time verifier, induced class is IP. Theorem [Shamir, 1992]: IP = PSPACE Concepts, Techniques, Idea & Proofs 1. 2. 3. 4. 5. 6.

7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 2-SAT 2-Way automata 3-colorability 3-SAT Abstract complexity Acceptance Ada Lovelace Algebraic numbers Algorithms Algorithms as strings Alice in Wonderland Alphabets Alternation Ambiguity Ambiguous grammars Analog computing Anisohedral tilings Aperiodic tilings Approximate min cut Approximate TSP 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32.

33. 34. 35. 36. 37. 38. 39. 40. Approximate vertex cover Approximations Artificial intelligence Asimovs laws of robotics Asymptotics Automatic theorem proving Autonomous vehicles Axiom of choice Axiomatic method Axiomatic system Babbages analytical engine Babbages difference engine Bin packing Binary vs. unary Bletchley Park Bloom axioms Boolean algebra Boolean functions Bridges of Konigsberg Brute fore 41. 42. 43. 44. 45. 46. 47. 48. 49. 50. 51. 52. 53. 54. 55. 56. 57. 58.

59. 60. Busy beaver problem C programs Canonical order Cantor dust Cantor set Cantors paradox CAPCHA Cardinality arguments Cartesian coordinates Cellular automata Chaos Chatterbots Chess-playing programs Chinese room Chomsky hierarchy Chomsky normal form Chomskyan linguistics Christofides heuristic Church-Turing thesis Clay Mathematics Institute Concepts, Techniques, Ideas & Proofs 61. 62. 63. 64. 65. 66. 67. 68. 69. 70. 71. 72. 73. 74. 75. 76. 77. 78. 79. Clique problem 80. Cloaking devices

81. Closure properties 82. Cogito ergo sum 83. Colorings 84. Commutativity 85. Complementation 86. Completeness 87. Complexity classes 88. Complexity gaps 89. Complexity Zoo 90. Compositions 91. Compound pendulums 92. Compressibility 93. Computable functions 94. Computable numbers 95. Computation and physics 96. Computation models 97. Computational complexity98. 99. Computational universality Computer viruses Concatenation Co-NP Consciousness and sentience Consistency of axioms Constructions Context free grammars Context free languages Context sensitive grammars Context sensitive languages Continuity Continuum hypothesis

Contradiction Contrapositive Cooks theorem Countability Counter automata Counter example Cross- product 100. 101. 102. 103. 104. 105. 106. 107. 108. 109. 110. 111. 112. 113. 114. 115. 116. 117. 118. 119. Crossing sequences Cross-product construction Cryptography DARPA Grand Challenge DARPA Math Challenges De Morgans law Decidability Deciders vs. recognizers Decimal number system Decision vs. optimization Dedekind cut Denseness of hierarchies Derivations Descriptive complexity Diagonalization Digital circuits Diophantine equations Disorder DNA computing

Domains and ranges Concepts, Techniques, Ideas & Proofs 120. 121. 122. 123. 124. 125. 126. 127. 128. 129. 130. 131. 132. 133. 134. 135. 136. 137. 138. 139. Dovetailing DSPACE DTIME EDVAC Elegance in proof Encodings Enigma cipher Entropy Enumeration Epsilon transitions Equivalence relation Euclids Elements Euclids axioms Euclidean geometry Eulers formula Eulers identity Eulerian tour Existence proofs Exoskeletons Exponential growth 140. 141. 142.

143. 144. 145. 146. 147. 148. 149. 150. 151. 152. 153. 154. 155. 156. 157. 158. 159. Exponentiation EXPSPACE EXPSPACE EXPSPACE complete EXPTIME EXPTIME complete Extended Chomsky hierarchy Fermats last theorem Fibonacci numbers Final states Finite automata Finite automata minimization Fixed-point theorem Formal languages Formalizations Four color problem Fractal art Fractals Functional programming Fundamental thm of Algebra 160. 161. 162. 163. 164. 165. 166. 167. 168.

169. 170. 171. 172. 173. 174. 175. 176. 177. 178. 179. Fundamental thm of Arith. Gadget-based proofs Game of life Game theory Game trees Gap theorems Garey & Johnson General grammars Generalized colorability Generalized finite automata Generalized numbers Generalized venn diagrams Generative grammars Genetic algorithms Geometric / picture proofs Godel numbering Godels theorem Goldbachs conjecture Golden ratio Grammar equivalence Concepts, Techniques, Ideas & Proofs 180. 181. 182. 183. 184. 185. 186. 187. 188. 189. 190. 191. 192. 193.

194. 195. 196. 197. 198. 199. Grammars Grammars as computers Graph cliques Graph colorability Graph isomorphism Graph theory Graphs Graphs as relations Gravitational systems Greibach normal form Grey goo Guess-and-verify Halting problem Hamiltonian cycle Hardness Heuristics Hierarchy theorems Hilberts 23 problems Hilberts program Hilberts tenth problem 200. 201. 202. 203. 204. 205. 206. 207. 208. 209. 210. 211. 212. 213. 214. 215. 216. 217. 218. 219.

Historical perspectives Household robots Hung state Hydraulic computers Hyper computation Hyperbolic geometry Hypernumbers Identities Immermans Theorem Incompleteness Incompressibility Independence of axioms Independent set problem Induction & its drawbacks Infinite hotels & applications Infinite loops Infinity hierarchy Information theory Inherent ambiguity Initial state 220. 221. 222. 223. 224. 225. 226. 227. 228. 229. 230. 231. 232. 233. 234. 235. 236. 237. 238. 239. Intelligence and mind Interactive proofs Intractability Irrational numbers JFLAP

Karps paper Kissing number Kleene closure Knapsack problem Lambda calculus Language equivalence Law of accelerating returns Law of the excluded middle Lego computers Lexicographic order Linear-bounded automata Local minima LOGSPACE Low-deg graph colorability Machine enhancements Concepts, Techniques, Ideas & Proofs 240. 241. 242. 243. 244. 245. 246. 247. 248. 249. 250. 251. 252. 253. 254. 255. 256. 257. 258. 259. Machine equivalence Mandelbrot set Manhattan project Many-one reduction Matiyasevichs theorem Mechanical calculator Mechanical computers Memes Mental poker Meta-mathematics

Millennium Prize Minimal grammars Minimum cut Modeling Multiple heads Multiple tapes Mu-recursive functions MAD policy Nanotechnology Natural languages 260. 261. 262. 263. 264. 265. 266. 267. 268. 269. 270. 271. 272. 273. 274. 275. 276. 277. 278. 279. Navier-Stokes equations Neural networks Newtonian mechanics NLOGSPACE Non-approximability Non-closures Non-determinism Non-Euclidean geometry Non-existence proofs NP NP completeness NP-hard NSPACE NTIME Occams razor Octonions

One-to-one correspondence Open problems Oracles P completeness 280. 281. 282. 283. 284. 285. 286. 287. 288. 289. 290. 291. 292. 293. 294. 295. 296. 297. 298. 299. P vs. NP Parallel postulate Parallel simulation Dovetailing simulation Parallelism Parity Parsing Partition problem Paths in graphs Peano arithmetic Penrose tilings Physics analogies Pi formulas Pigeon-hole principle Pilotless planes Pinwheel tilings Planar graph colorability Planarity testing Polyas How to Solve It Polyhedral dissections Concepts, Techniques, Ideas & Proofs

300. 301. 302. 303. 304. 305. 306. 307. 308. 309. 310. 311. 312. 313. 314. 315. 316. 317. 318. 319. Polynomial hierarchy Polynomial-time P-time reductions Positional # system Power sets Powerset construction Predicate calculus Predicate logic Prime numbers Principia Mathematica Probabilistic TMs Proof theory Propositional logic PSPACE PSPACE completeness Public-key cryptography Pumping theorems Pushdown automata Puzzle solvers Pythagorean theorem 320. 321. 322. 323. 324. 325.

326. 327. 328. 329. 330. 331. 332. 333. 334. 335. 336. 337. 338. 339. Quantifiers Quantum computing Quantum mechanics Quaternions Queue automata Quine Ramanujan identities Ramsey theory Randomness Rational numbers Real numbers Reality surpassing Sci-Fi Recognition and enumeration Recursion theorem Recursive function theory Recursive functions Reducibilities Reductions Regular expressions Regular languages 340. 341. 342. 343. 344. 345. 346. 347. 348. 349. 350. 351.

352. 353. 354. 355. 356. 357. 358. 359. Rejection Relations Relativity theory Relativization Resource-bounded comput. Respect for the definitions Reusability of space Reversal Reverse Turing test Rices Theorem Riemann hypothesis Riemanns zeta function Robots in fiction Robustness of P and NP Russells paradox Satisfiability Savitchs theorem Schmitt-Conway biprism Scientific method Sedenions Concepts, Techniques, Ideas & Proofs 360. 361. 362. 363. 364. 365. 366. 367. 368. 369. 370. 371. 372. 373. 374. 375. 376.

377. 378. 379. Self compilation Self reproduction Set cover problem Set difference Set identities Set theory Shannon limit Sieve of Eratosthenes Simulated annealing Simulation Skepticism Soundness Space filling polyhedra Space hierarchy Spanning trees Speedup theorems Sphere packing Spherical geometry Standard model State minimization 380. 381. 382. 383. 384. 385. 386. 387. 388. 389. 390. 391. 392. 393. 394. 395. 396. 397. 398. 399. Steiner tree Stirlings formula

Stored progam String theory Strings Strong AI hypothesis Superposition Super-states Surcomplex numbers Surreal numbers Symbolic logic Symmetric closure Symmetric venn diagrams Technological singularity Theory-reality chasms Thermodynamics Time hierarchy Time/space tradeoff Tinker Toy computers Tractability 400. 401. 402. 403. 404. 405. 406. 407. 408. 409. 410. 411. 412. 413. 414. 415. 416. 417. 418. 419. Tradeoffs Transcendental numbers Transfinite arithmetic Transformations Transition function Transitive closure Transitivity Traveling salesperson

Triangle inequality Turbulance Turing complete Turing degrees Turing jump Turing machines Turing recognizable Turing reduction Turing test Two-way automata Type errors Uncomputability Concepts, Techniques, Ideas & Proofs 420. 421. 422. 423. 424. 425. 426. 427. 428. 429. 430. Uncomputable functions Uncomputable numbers Uncountability Undecidability Universal Turing machine Venn diagrams Vertex cover Von Neumann architecture Von Neumann bottleneck Wang tiles & cubes Zero-knowledge protocols . . . . Make everything as simple as possible, but not simpler. - Albert Einstein (1879-1955)