NP-complete problems: Samuel's tutorial скачать в хорошем качестве

NP-complete problems: Samuel's tutorial

Samuel's tutorial for NP-complete problems (history, definitions and reduction strategy). Timestamps: 00:00 - NP-complete problems: Samuel's tutorial 00:37 - The Entscheidungsproblem (Decision Problem) 02:32 - Godel And Herbrand 03:54 - Church And Turing 05:48 - Algorithmic Efficiency 07:22 - P Versus NP 09:11 - NP-complete And NP-hard 10:16 - Strategy To Show NP-Completeness 11:45 - Polynomial-time Reductions 13:18 - A First NP-complete Problem 14:03 - Problems Solvable In Polynomial Time 15:12 - Formal Definitions: Problems And Encodings 16:29 - A Definition For Complexity Class P 17:43 - Formal-Language Theory Definitions 19:02 - Formal-Language Notation 20:27 - Alternative Definition Of P 21:36 - Hamiltonian And Eulerian Cycles 23:02 - Polynomial-time Verification And NP 24:38 - Reducibility 26:07 - NP-completeness Detailed description: This video begins with a short history of the "Entscheidungsproblem" (decision problem) introduced by Hilbert and Ackerman in 1928. Next, we describe the work of Godel and Herbrand, and how it implicitly ruled out a solution. We then turn to the efforts of Church and Turing, who contributed independent formal proofs that no general procedure could be found to decide if an arbitrary proposition is provable from axioms of first-order logic. Turing's work on the halting problem, in particular, highlighted that many problems simply cannot be solved at all! We then turn to algorithmic efficiency, adopting the convention (known as Cobham's thesis) that problems that can be solved in polynomial-time algorithms are tractable. These are distinguished from those problems whose answer is "yes" and which can be verified in polynomial time (NP) and problems whose answer is "no" and which can be verified in polynomial time (co-NP). Next, we introduce the P versus NP problem, a Millenium Prize problem that remains unsolved. We distinguish NP-complete and NP-hard problems and visualise their relationship according to how every reasonable human sees the world (i.e. P != NP). We then describe a strategy for showing that a problem is NP-complete, which builds on three pillars: (1) converting optimisation problems to decision problems; (2) polynomial-time reductions; and (3) a first NP-complete problem (the Cook-Levin Theorem). Next, we examine in more detail some practical reasons why problems solvable in polynomial time are considered tractable. We then turn to formal definitions of problems and encodings, and a definition for the complexity class P. The last part of the video focuses on formal-language theory. We introduce a host of definitions that link decision problems and the algorithms that solve them, and introduce the notion of "accepting" a language and "deciding" a language. Within this framework, we provide an alternative definition of P and describe polynomial-time verification and NP. We conclude with a discussion of reducibility and NP-completeness. Topics: #NP-completeness #PvsNP #NP-hard Slides (pdf): https://samuelalbanie.com/files/diges... References for papers mentioned in the video can be found at http://samuelalbanie.com/digests/2023... For related content: Twitter:   / samuelalbanie   Research lab: https://caml-lab.com/ personal webpage: https://samuelalbanie.com/ YouTube:    / @samuelalbanie1