1 Uniwersytet ZielonogórskiJak wygrać $ w Sapera ? Tomasz Bartnicki Uniwersytet Zielonogórski

2

3 Rok 1900, Paryż 23 problemy Musimy wiedzieć! Będziemy wiedzieć!David Hilbert ( ) Musimy wiedzieć! Będziemy wiedzieć! 23 problemy

4 Rok 2000, Paryż Problemy milenijne, $1.000.000 za każdy1. Hipoteza Poincarego rozwiązana! (Grigorij Perelman) 2. Hipoteza Riemanna (8. problem Hilberta) 3. Równanie Naviera-Stokesa 4. Teoria Yanga-Millsa 7. Hipoteza P kontra NP 5. Hipoteza Hodge’a 6. Hipoteza Bircha i Swinnertona-Dyera 7. Hipoteza P kontra NP

5 Historia problemu P kontra NPAlan Turing ( ) Maszyna Turinga (1936) Stephen A. Cook 1971- pierwsze(?) precyzyjne sformułowanie hipotezy P/NP 1982- Nagroda Turinga

6 Klasa P (polynomial) T(n)Algorytm Rozwiązanie TAK NIE CPU Problem Rozmiar danych: n Czas pracy: T(n) Jeżeli dla problemu istnieje „szybki” algorytm rozwiązujący go, to mówimy, że problem należy do klasy P. (wielomian) Szybki:

7 Przykłady problemów P Znajdowanie wzorca w tekście

8 Przykłady problemów P Znajdowanie wzorca w tekścieDwukolorowanie grafu

9 Przykłady problemów P Znajdowanie wzorca w tekścieDwukolorowanie grafu Cykl Eulera w grafie 7 mostów w Królewcu Leonard Euler ( )

10 Przykłady problemów P Znajdowanie wzorca w tekścieDwukolorowanie grafu Cykl Eulera w grafie Sprawdzenie czy liczba jest pierwsza

11 P NP Klasa NP (nonderministic-polynomial) T(n)Algorytm Problem Rozmiar danych: n Weryfikacja TAK NIE CPU Czas pracy: T(n) Potencjalne rozwiązanie Jeżeli dla problemu istnieje „szybki” algorytm weryfikujący rozwiązanie, to mówimy, że problem należy do klasy NP. P NP

12 Przykłady problemów NPPuzzle

13 Przykłady problemów NPPuzzle Trójkolorowanie grafu

14 Przykłady problemów NPPuzzle Trójkolorowanie grafu Cykl Hamiltona w grafie

15 Przykłady problemów NPPuzzle Trójkolorowanie grafu Cykl Hamiltona w grafie

16 Przykłady problemów NPPuzzle Trójkolorowanie grafu Cykl Hamiltona w grafie

17 Przykłady problemów NPPuzzle Trójkolorowanie grafu Cykl Hamiltona w grafie Problem pirata komputerowego

18 P NP P NP Sformułowanie problemu Fakt: Domniemanie: Hipoteza: Dowód…?łatwa rozwiązywalność łatwa weryfikowalność Domniemanie: łatwa weryfikowalność łatwa rozwiązywalność P NP Hipoteza: Dowód…?

19 NP-zupełność NP P NP-zupełneProblem z klasy NP nazywamy NP-zupełnym, jeżeli każdy problem z NP redukuje się do niego w czasie wielomianowym. Problemy NP-zupełne, są najtrudniejsze w klasie NP. NP P NP-zupełne

20 NP-zupełność NP P NP-zupełneProblem z klasy NP nazywamy NP-zupełnym, jeżeli każdy problem z NP redukuje się do niego w czasie wielomianowym. Problemy NP-zupełne, są najtrudniejsze w klasie NP. NP P NP-zupełne

21 NP-zupełność P = NP = NP-zupełneProblem z klasy NP nazywamy NP-zupełnym, jeżeli każdy problem z NP redukuje się do niego w czasie wielomianowym. Problemy NP-zupełne, są najtrudniejsze w klasie NP. P = NP = NP-zupełne

22 Problemy NP-zupełne Pierwszy problem NP-zupełny (Stephen Cook, 1971)Spełnialność formuł logicznych (3SAT)

23 Problemy NP-zupełne Pierwszy problem NP-zupełny (Stephen Cook, 1971)Spełnialność formuł logicznych (3SAT) Problem kliki w grafie

24 Problemy NP-zupełne Pierwszy problem NP-zupełny (Stephen Cook, 1971)Spełnialność formuł logicznych (3SAT) Problem kliki w grafie Dowód NP-zupełności:

25 Problemy NP-zupełne Pierwszy problem NP-zupełny (Stephen Cook, 1971)Spełnialność formuł logicznych (3SAT) Problem kliki w grafie Dowód NP-zupełności:

26 Problemy NP-zupełne Pierwszy problem NP-zupełny (Stephen Cook, 1971)Spełnialność formuł logicznych (3SAT) Problem kliki w grafie Dowód NP-zupełności:

27 Problemy NP-zupełne Pierwszy problem NP-zupełny (Stephen Cook, 1971)Spełnialność formuł logicznych (3SAT) Problem kliki w grafie Dowód NP-zupełności:

28 Problemy NP-zupełne Pierwszy problem NP-zupełny (Stephen Cook, 1971)Spełnialność formuł logicznych (3SAT) Problem kliki w grafie Dowód NP-zupełności:

29 …i kilkaset innych problemówProblemy NP-zupełne Pierwszy problem NP-zupełny (Stephen Cook, 1971) Spełnialność formuł logicznych (3SAT) Problem kliki w grafie …i kilkaset innych problemów Trójkolorowanie grafu Cykl Hamiltona w grafie Problem pirata komputerowego

30 Saper jest trudny Zadanie 1. Zadanie 2. Zadanie 3.

31 Saper jest trudny MCP jest problemem NP-zupełnym Zadanie 1. Zadanie 2.Zadanie 4. Minesweeper Consistency Problem (MCP) Czy zadany układ początkowy z Sapera ma rozwiązanie? MCP jest problemem NP-zupełnym Richard Kaye Minesweeper is NP-complete, Mathematical Intelligencer, (2000)

32 NP-zupełność Sapera 3SAT MCP formuła logiczna obwód logicznywielomianowa redukcja formuła logiczna obwód logiczny konfiguracja Sapera przewód logiczny wejście wyjście 1

33 NP-zupełność Sapera 1 1 negacja - bramka NOT 1 koniunkcja – bramka AND1 1 koniunkcja – bramka AND alternatywa – bramka OR 1 1

34 Przykład

35 Zamiast rozstrzygnięciaAnkieta na temat P/NP (2002) 22 głosy: 3 głosy: 4 głosy: 1 głos: 61 głosów: 9 głosów: P NP Nie mam zdania P NP Niezależna od aksjomatów teorii mnogości Nie jest niezależna od aksjomatów arytmetyki Zależy od przyjętego modelu William Gasarch Kiedy zostanie rozstrzygnięta? 2050 rok (wartość środkowa z 79 odpowiedzi)

36 Zamiast zakończenia Kurt Godel ( ) .. Dziękuję