Nauczanie kompletności NP - redukcje Turinga i karp

Interesuje mnie pytanie, jak najlepiej uczyć kompletności NP na kierunkach informatycznych. W szczególności, czy powinniśmy tego uczyć stosując redukcje Karp czy redukcje Turinga?

Uważam, że koncepcje kompletności i redukcji NP są czymś, czego powinien nauczyć się każdy kierunek informatyki. Jednak ucząc kompletności NP zauważyłem, że stosowanie redukcji Karp ma pewne wady.

Po pierwsze, obniżenie Karp wydaje się być niepotrzebnie mylące dla niektórych uczniów. Intuicyjnym pojęciem redukcji jest „jeśli mam algorytm do rozwiązania problemu X, to mogę go również użyć do rozwiązania problemu Y”. To bardzo intuicyjne - ale znacznie lepiej odwzorowuje redukcje Turinga niż redukcje Karp. W rezultacie widzę studentów, którzy próbują udowodnić kompletność NP, zostają wprowadzeni w błąd przez swoją intuicję i tworzą niepoprawny dowód. Próba nauczenia obu rodzajów redukcji i podkreślenie tego aspektu redukcji Karp czasami wydaje się trochę niepotrzebnym formalizmem i zajmuje niepotrzebny czas na zajęciach oraz uwagę uczniów na to, co wydaje się być nieistotnym szczegółem technicznym; nie jest oczywiste, dlaczego używamy tego bardziej ograniczonego pojęcia redukcji.

Rozumiem różnicę między redukcjami Karp a redukcjami Turinga (Cooka) i jak prowadzą one do różnych pojęć kompletności NP. Zdaję sobie sprawę, że redukcje Karp dają nam większą szczegółowość rozróżnienia między klasami złożoności. Tak więc, do poważnego badania teorii złożoności, redukcje Karp są oczywiście właściwym narzędziem. Ale dla studentów informatyki, którzy dopiero się tego uczą i nigdy nie zamierzają zagłębiać się w teorię złożoności, nie jestem pewien, czy to lepsze rozróżnienie jest krytyczne, ma dla nich kluczowe znaczenie.

Wreszcie, jako student, pamiętam, że czułem się zdziwiony, gdy natknąłem się na problem taki jak „tautologia” - np. Biorąc pod uwagę logiczną formułę, sprawdź, czy jest to tautologia. Mylące było to, że ten problem jest wyraźnie trudny: każdy algorytm wielomianowy sugerowałby, że $P=NP$; a rozwiązanie tego problemu jest oczywiście tak samo trudne jak rozwiązanie problemu tautologii. Jednak choć intuicyjnie tautologia jest tak trudna, jak satysfakcja, tautologia nie jest trudna NP. Tak, rozumiem dzisiaj, dlaczego tak jest, ale w tym momencie pamiętam, że byłem tym zaskoczony. (Po tym, jak w końcu zrozumiałem, przeszło mi przez myśl: dlaczego w każdym razie rozróżniamy między NP-twardym a co-NP-twardym? To wydaje się sztuczne i niezbyt dobrze motywowane praktyką. Dlaczego skupiamy się na NP niż co-NP? Wydają się równie naturalne. Z praktycznego punktu widzenia twardość co-NP wydaje się mieć zasadniczo takie same praktyczne konsekwencje jak twardość NP, więc dlaczego wszyscy rozłączamy się z tym rozróżnieniem? Tak, wiem odpowiedzi, ale jako student pamiętam, że właśnie to sprawiło, że przedmiot był bardziej tajemniczy i słabo umotywowany).

Więc moje pytanie brzmi: Kiedy uczymy uczniów kompletności NP, czy lepiej uczyć stosując redukcje Karp lub redukcje Turinga? Czy ktoś próbował nauczać pojęcia kompletności NP za pomocą redukcji Turinga? Jeśli tak, jak poszło? Czy wystąpiłyby jakieś nieoczywiste pułapki lub wady, gdybyśmy uczyli pojęć stosując redukcje Turinga i pomijaliśmy kwestie koncepcyjne związane z redukcjami Karp?

Powiązane: patrz tutaj i tutaj , które wspominają, że powodem, dla którego stosujemy redukcje Karpa w literaturze, jest to, że pozwala nam odróżnić twardość NP od twardości co-NP. Wydaje się jednak, że nie daje żadnej odpowiedzi, która koncentrowałaby się na pedagogicznej perspektywie tego, czy ta umiejętność jest kluczowa dla celów uczenia się klasy algorytmów, które powinny być podejmowane przez każdego kierownika CS. Zobacz także tutaj na cstheory.SE , który ma podobną dyskusję.

Powiedziałbym, że zdecydowanie nauczam, używając redukcji Karp (wiele jeden). Niezależnie od korzyści wynikających z zastosowania wieloczasowych redukcji Turinga (Cook), redukcje Karp są standardowym modelem.

Wszyscy używają Karpa, a główną pułapką nauczania Cooka jest to, że skończysz z całą klasą uczniów, którzy będą patologicznie zdezorientowani za każdym razem, gdy czytają podręcznik lub próbują dyskutować na ten temat z każdym, kto nie był przez ciebie nauczany.

Zgadzam się, że redukcje Cooka są pod kilkoma względami bardziej sensowne i że nie ma rozróżnienia między twardością NP i twardością CoNP w sensie praktycznym, w tym sensie, że oba oznaczają „Ten problem jest dość trudny i nie dostaniesz ogólny, wydajny, dokładny algorytm, który poradzi sobie z dużymi instancjami. ” Z drugiej strony rozróżnienie między NP a coNP nie jest wyłącznie artefaktem teorii opartej na redukcjach Karp: często nie mówimy o wykresach, które nie są 3-kolorowe, lub w których każdy zestaw  wierzchołków zawiera przynajmniej jedna krawędź. Jakoś „naturalna” wersja problemu często wydaje się być w NP, a nie w CoNP.$k$

Lepiej uczyć obu ! Kierunek informatyki powinien wiedzieć o nich obu.

Nie znam nikogo, kto użyje obniżek Cooka do nauczania kompletności NP, teoretycy złożoności oczywiście nie, teoretycy nieskomplikowani zwykle podążają za standardową definicją od czasu pracy Karpa i są używane we wszystkich podręcznikach (o których wiem). Spowoduje to później wiele zamieszania, jeśli nie zastosujesz się do standardowej terminologii.

Redukcje gotowania zasadniczo rozwiązują problemy przy użyciu podprogramów czarnej skrzynki. Łatwo je wyjaśnić i zmotywować, jeśli Twoi uczniowie mają doświadczenie w programowaniu. Są one niezbędne, ponieważ bez redukcji Cooka nie można omawiać redukcji między problemami wyszukiwania, problemami optymalizacji itp.

$\mathsf{NP}$$\mathsf{NP}$$\mathsf{P}^{\mathsf{NP}}$$\mathsf{NP}$

$\mathsf{NP}$$\mathsf{coNP}$$\mathsf{NP}$$\mathsf{NP}$$\mathsf{NP}$$\mathsf{P}^{\mathsf{NP}}$

$x\in A$$f(x) \in B$

Intuicyjnym pojęciem redukcji jest „jeśli mam algorytm do rozwiązania problemu X, to mogę go również użyć do rozwiązania problemu Y”.

interesującym sposobem podejścia do tego konkretnego problemu nauczania jest uświadomienie sobie, że kompletność NP ma podobieństwa i analogie do nierozstrzygalności, co również jest nieintuicyjne. uczniowie wchodzą na zajęcia tylko wtedy, gdy słyszą o algorytmach, które się zatrzymują. ale głównym twierdzeniem TCS jest to, że istnieją problemy, dla których nie ma gwarantowanego rozwiązania, tj. problem zatrzymania. w rzeczywistości nierozwiązywalne problemy mogą zacząć wyglądać na dalekie od wymyślonych i są najwyraźniej dość wszechobecne.

więc teoria mówi nam, w jaki sposób można zasadniczo spojrzeć na obliczenia jako proces, który może w pewnych okolicznościach zwrócić odpowiedź. w innych okolicznościach może nie. dla kompletności i rozstrzygalności NP podstawowe i najbardziej ogólne pytanie brzmi: „czy istnieje algorytm, który zwraca się Yw czasie P.” ale to nic nie mówi o algorytmie, który zwraca Nw czasie P. algorytm może zwrócić Yw czasie P dla jednej instancji, ale nie może zwrócić odpowiedzi w innych instancjach. teoria mówi nam, że naprawdę jest tutaj wyraźna różnica, na którą musimy zwrócić szczególną uwagę. jeśli jest to nieintuicyjne, oznacza to, że nasze podstawowe intuicje muszą zostać ponownie dostosowane (jak to często bywa w nauczaniu teoretycznym).