Wyjaśnianie SAT nauczycielom przedmiotów ścisłych w szkole średniej

9

Jestem absolwentem liceum, który interesuje się informatyką. Opracowałem fajny algorytm dla #SAT i wdrażam na nim projekt Science Fair. Mój doradca, który jest najlepszym nauczycielem przedmiotów ścisłych w mojej szkole i nauczycielem AP Comp Sci, powiedział mi, że absolutnie nie ma pojęcia, o czym jest mój projekt, i że muszę krótko wyjaśnić, dlaczego #SAT jest ważne w mniej niż 5 minut. Powiedziałem jej, że SAT redukuje się do #SAT i próbowałem wyjaśnić, dlaczego SAT jest ważny: podałem jej kilka przykładów problemów z NP, wyjaśniłem jej, w jaki sposób problemy z NP redukują się do SAT, i wyjaśniłem, w jaki sposób dzięki wyszukiwaniu binarnemu możesz zredukować niektóre problemy optymalizacji do SAT , który pozwala składać białka i tworzyć potężne modele AI. Niestety w ogóle mnie nie zrozumiała. Czy możesz podać mi kilka wskazówek?

PS Mój doradca zapytał mnie, jakie przydatne problemy redukują do #SAT, które nie redukują do SAT (zakładając, że niektóre problemy w #P są trudniejsze niż odpowiadające im wersje NP). Mogłem tylko wymyślić, ile modeli dla danego zestawu danych jest lepszych niż dany model (zakładając, że każdy parametr modelu jest mniejszy niż określona liczba bitów). Szukałem innych w Internecie, ale nie mogłem znaleźć niczego, co mógłbym zrozumieć. Czy są jakieś inne dobre aplikacje?

Elliot Gorokhovsky
źródło
2
Stała (nawet dla macierzy, których wpisy są ograniczone do 0 lub 1) ma wartość # P-complete, więc wszelkie aplikacje stałej są również aplikacjami twojego algorytmu, o ile aplikacje te wymagają obliczenia (lub przybliżenia) stałej jakiejś matrycy „w praktyce” (raczej niż na papierze).
Yuval Filmus
wybrałeś doskonały projekt teoretyczny, ale niezbyt zaawansowany / abstrakcyjny dla liceum. oczywiste pytanie, jak sam dowiedziałeś się o znaczeniu #SAT? mogą istnieć pewne powiązania np. z programem nauczania AP CS poprzez NP kompletność itp., czy wziąłeś już tę klasę? z jakiego podręcznika się korzysta? jeśli jest dobry, będą tam pewne połączenia z moimi. zasugeruj, że wpadniesz na czat z informatyki w celu uzyskania porady, spędza tam kilku studentów / doktorantów. a także zaprosić Cię do salonu cstheory, aby omówić go dalej.
vzn
Gdybym musiał to wyjaśnić odbiorcom spoza CS / nie matematyki, wyjaśniłbym: (1) na czym polega problem (oczekujesz pewnego rodzaju danych wejściowych i chcesz stworzyć wyniki oparte na tych danych wejściowych), ( 2) wyjaśnić, co to znaczy być trudnym, (3) wyjaśnić problemy SAT i #SAT, (4) stwierdzić, że problemy te są trudne, i (5) stwierdzić, że znalezienie szybszych algorytmów problemów ogólnie jest wysoko cenione wystarczy, że pojawi się nagroda w wysokości miliona dolarów, jeśli szybko rozwiążesz problem SAT. Mam nadzieję, że to trochę pomoże, chociaż nie do końca odpowiada na twoje pytania. Miłego dnia!
Michael Wehar,
Istnieje kilka problemów wymienionych na Wikipedii (chociaż prawdopodobnie już to widziałeś). Oto link: en.wikipedia.org/wiki/Sharp-P
Michael Wehar
1
@MichaelWehar Chociaż gdybyś mógł szybko rozwiązać SAT, milion dolarów nie byłby dla ciebie wiele wart!
Elliot Gorokhovsky,

Odpowiedzi:

6

Trwałe jest # P-pełne, nawet jeśli jest ograniczone do {0,1}- wycenione macierze. Stała może być użyta do obliczenia niektórych parametrów w mechanice statystycznej, patrz na przykład ten artykuł na temat problemu pokrycia dimeru. Ponieważ nie jestem fizykiem, nie mogę komentować, czy te teoretyczne problemy z mechaniką statystyczną są naprawdę przydatne; Podejrzewam, że nie są one bezpośrednio przydatne, ale sam obszar może prowadzić do użytecznych informacji. Może się zdarzyć, że niektóre z tych parametrów są przydatne same z siebie, ale będziesz musiał skonsultować się z ekspertem.

Twoje 5-minutowe boisko może wyglądać mniej więcej tak:

Mechanika statystyczna to piękna i głęboka część fizyki i chemii, która bada, w jaki sposób powstające zachowanie dużych układów wynika z mikroskopijnych praw fizycznych działających na poszczególne elementy. Wyjaśnia takie zjawiska, jak prawa gazów, magnetyzacja i przejścia między różnymi fazami materii. Mechanika statystyczna jest ściśle związana z teorią prawdopodobieństwa, informatyką, badaniami operacyjnymi i nauką danych.

Wiele ważnych wielkości w mechanice statystycznej można sformułować jako instancje #SAT. Algorytm rozwiązywania dokładnie #SAT dokładnie lub w przybliżeniu można zatem wykorzystać do przewidywania zjawisk fizycznych i chemicznych.

Może to nieco przesadzić ze sprawą, ale tak wyglądają wzrosty sprzedaży.

Yuval Filmus
źródło
1

To pytanie wydaje się mieszać trochę SAT i #SAT w swoim brzmieniu. Tak, oba są ze sobą ściśle powiązane. #SAT jest po prostu zdefiniowany jako klasa złożoności związana z zliczaniem liczby rozwiązań problemu SAT i powszechnie przypuszcza się, że jest znacznie trudniejszy, ale może, co zaskakujące, nie został udowodniony . #SAT nie jest nawet przedmiotem badań w teorii złożoności na poziomie uczelni, jest bardziej zaawansowanym tematem badań teoretycznych.

Jednym ze sposobów na uzasadnienie znaczenia #SAT jest twierdzenie Tody, które wygrało nagrodę Gödela w 1998 roku za jego głębokie znaczenie. Z Wikipedii:

Twierdzenie Tody implikuje zatem, że dla każdego problemu w hierarchii wielomianowej istnieje deterministyczna redukcja Turinga w czasie wielomianowym do problemu zliczania. [1]

Ponadto, ponieważ nie udowodniono nawet, że SAT i #SAT mają różną złożoność, można uzasadnić, że zrozumienie złożoności #SAT może prowadzić do pewnego wglądu w problem P i NP , który ma mnóstwo informacji i motywacji .

vzn
źródło
re P vs NP patrz także ostatnia książka Fortnow Golden ticket, P / NP i poszukiwanie niemożliwego
vzn
Każda aplikacja SAT jest aplikacją #SAT, szukam aplikacji obu.
Elliot Gorokhovsky,
lol to twoje pytanie jest zupełnie inne. Całkowite problemy NP mają bardzo szerokie zastosowania i jest to szeroko udokumentowane. patrz książka Fortnows lub np. teoria kompletności NP Gareya / Johnsona . i btw, jeśli nauczyciel AP CS nie wie, co to jest kompletność NP, to powinien zostać zwolniony.
vzn
Cóż, dzieci biorące udział w zajęciach nie rozumieją nawet prostych pojęć, takich jak wyszukiwanie binarne, więc gdyby wiedziała o tym, to i tak zmarnowałoby to na uszy uczniów.
Elliot Gorokhovsky,
Czy potrafisz też wyjaśnić, dlaczego trudno udowodnić twierdzenie Tody? Ponieważ ponieważ każdy problem w NP redukuje się do SAT, co w uproszczeniu sprowadza się do #SAT. Jakie problemy występują w PH, których nie ma w NP? Przepraszam, nauczyłem się wszystkiego z Wikipedii, więc mam mnóstwo dziur w swojej wiedzy.
Elliot Gorokhovsky