Tài liệu miễn phí Toán học
Download Tài liệu học tập miễn phí Toán học
Theory of Computation: Lecture 45. The main topics covered in this lesson include: space complexity; computability; non-trivial semantic properties; post correspondence problem; Presburger arithmetic; the Gödel’s theorem; the Clay mathematical society;...
4/8/2023 4:26:12 PM +00:00
Theory of Computation: Lecture 44. The main topics covered in this lesson include: space complexity; non-deterministic algorithm; non-deterministic LOGSPACE; highly non-deterministic program; the space requirements;...
4/8/2023 4:26:05 PM +00:00
Theory of Computation: Lecture 43. The main topics covered in this lesson include: space complexity; Savatich’s theorem; non-deterministic algorithm; the initial configuration; the contents of the work tape and the machine is currently reading the i-th symbol on the work tape and the j-th symbol of the input;...
4/8/2023 4:25:57 PM +00:00
Theory of Computation: Lecture 42. The main topics covered in this lesson include: space complexity; new complexity classes; interesting space complexity classes; non-deterministic analogue; Savatich’s theorem; polynomial time reducibility;...
4/8/2023 4:25:49 PM +00:00
Theory of Computation: Lecture 41. The main topics covered in this lesson include: space complexity; generalized geography; polynomial time algorithm; algorithm requires polynomial space; the existentially quantified variables; the universally quantified variables;...
4/8/2023 4:25:42 PM +00:00
Theory of Computation: Lecture 40. The main topics covered in this lesson include: true fully quantified boolean formula (TQBF); FORMULA-GAME; generalized geography; alternating quantified formula; combinatorial games;...
4/8/2023 4:25:35 PM +00:00
Theory of Computation: Lecture 39. The main topics covered in this lesson include: space complexity; true fully quantified boolean formula (TQBF); prove that TQBF is PSPACE-complete; other PSPACE-complete problems; polynomial space;...
4/8/2023 4:25:29 PM +00:00
Theory of Computation: Lecture 38. The main topics covered in this lesson include: relationship between space and time complexity; PSPACE; PSPACE-completeness and PSPACE-complete language; TQBF; non-trivial relationships; favorite complexity classes;...
4/8/2023 4:25:22 PM +00:00
Theory of Computation: Lecture 36. The main topics covered in this lesson include: space complexity; deterministic space complexity; non-deterministic space complexity; examples of space efficient TMs; reachability problem; Savitch’s theorem;...
4/8/2023 4:25:09 PM +00:00
Theory of Computation: Lecture 35. The main topics covered in this lesson include: Traveling Salesman Problem (TSP); the metric TSP; approximation algorithm and an approximation algorithm for the TSP problem; space complexity; the PCP theorem and hardness of approximation;...
4/8/2023 4:25:02 PM +00:00
Theory of Computation: Lecture 34. The main topics covered in this lesson include: three versions of the TSP problem; an approximation algorithm for the TSP problem; space complexity; polynomial time algorithm; the euclidean TSP;...
4/8/2023 4:24:56 PM +00:00
Theory of Computation: Lecture 33. The main topics covered in this lesson include: TSP problem; polynomial time algorithm; the subset sum problem; NP-completeness; multi-set of positive integers;...
4/8/2023 4:24:49 PM +00:00
Theory of Computation: Lecture 32. The main topics covered in this lesson include: NP-completeness; review of NP-completeness results; hamiltonian path problem; the diamond shape structure; the satisfying assignments; vertex vover;...
4/8/2023 4:24:43 PM +00:00
Theory of Computation: Lecture 29-30. The main topics covered in this lesson include: NP-completeness; Cook-Levin theorem; polynomial time reducible; conjunctive normal form (CNF); verification algorithm; independent sets;...
4/8/2023 4:24:36 PM +00:00
Theory of Computation: Lecture 28. The main topics covered in this lesson include: the Cook-Levin theorem; polynomial time; propositional logic; algorithm computes a function in polynomial time; polynomial time reducibility;...
4/8/2023 4:24:28 PM +00:00
Theory of Computation: Lecture 27. The main topics covered in this lesson include: satisfiability; verification algorithm; Cook-Levin theorem; non-deterministic Turing machine; non-deterministic polynomial time; schematic diagram;...
4/8/2023 4:24:19 PM +00:00
Theory of Computation: Lecture 26. The main topics covered in this lesson include: NP-completness; satisfiability; Cook-Levin theorem; 3-colorable; translation algorithm; polynomial-time reducibility; non-deterministic turing machines;...
4/8/2023 4:24:12 PM +00:00
Theory of Computation: Lecture 25. The main topics covered in this lesson include: verification algorithms; subsetsum problem; alternate characterization of NP; the P versus NP question; polynomial time reducibility; NP completeness; satisfiability; Cook-Levin theorem;...
4/8/2023 4:24:06 PM +00:00
Theory of Computation: Lecture 23. The main topics covered in this lesson include: the class NP; polynomial time verifiers; examples of problems in NP; non-deterministic TM; non-deterministic polynomial time algorithm; polynomial time non-deterministic turing machies;...
4/8/2023 4:23:59 PM +00:00
Theory of Computation: Lecture 22. The main topics covered in this lesson include: non-deterministic time; the class P; the class NP; time complexity classes; time deterministic single tape TM; polynomial time algorithm; adjacency matrix; adjacency list; non-deterministic analog;...
4/8/2023 4:23:48 PM +00:00
Theory of Computation: Lecture 21. The main topics covered in this lesson include: big-Oh notation; little-o notation; time complexity classes; non-deterministic TMs; the class P; resource bounded computations; non-deterministic finite automata; non-deterministic pushdown automata;...
4/8/2023 4:23:37 PM +00:00
Theory of Computation: Lecture 20. The main topics covered in this lesson include: incompressible strings; minimal length descriptions; descriptive complexity; complexity theory; big O notation and small o notation;...
4/8/2023 4:23:30 PM +00:00
Theory of Computation: Lecture 19. The main topics covered in this lesson include: a definition of information; minimal length descriptions; descriptive complexity; Kolmogorov complexity and 2 Kolmogorov-Chaitin complexity; optimality of definition;...
4/8/2023 4:23:23 PM +00:00
Theory of Computation: Lecture 18. The main topics covered in this lesson include: oracle turing machines; turing reducibility; berry paradox; a definition of information; minimal length descriptions; descriptive complexity;...
4/8/2023 4:23:17 PM +00:00
Theory of Computation: Lecture 17. The main topics covered in this lesson include: undecidability of logical theories; peano arithmetic; undecidability of peano arithmetic; Gödel’s incompleteness theorem;...
4/8/2023 4:23:10 PM +00:00
Theory of Computation: Lecture 16. The main topics covered in this lesson include: logical theories and decidability of logical theories; presburger arithmetic; decidability of presburger arithmetic;...
4/8/2023 4:22:59 PM +00:00
Theory of Computation: Lecture 15. The main topics covered in this lesson include: recursion theorem; some applications of recursion theorem; mathematical logic and decidability of logical theories; scrambles programs;...
4/8/2023 4:22:52 PM +00:00
Theory of Computation: Lecture 14. The main topics covered in this lesson include: reducibility; un-Turing-recognizability; a nice puzzle; programs that print themselves; recursion theorem; programming languages version;...
4/8/2023 4:22:43 PM +00:00
Theory of Computation: Lecture 13. The main topics covered in this lesson include: computable functions; reducibility; reducibility and undecidability; reducibility and un-Turing-recognizability;...
4/8/2023 4:22:35 PM +00:00
Theory of Computation: Lecture 12. The main topics covered in this lesson include: post correspondence problem; PCP is undecidable; computable functions and examples of computable functions; reducibility;...
4/8/2023 4:22:28 PM +00:00