P a NP i inne obliczenia ograniczone do zasobów.
Norbert Blum opublikował niedawno 38-stronicowy dowód, że . Czy to jest poprawne?P.≠ N.P.P≠NPP \ne NP Także na temat: gdzie jeszcze (w Internecie) omawia się jego poprawność? Uwaga: zakres tego tekstu pytania zmienił się z czasem. Szczegóły znajdują się w komentarzach do...
Rozkładanie na czynniki i izomorfizm wykresów są problemami w NP, o których nie wiadomo, że są w P ani w NP-kompletne. Jakie są inne (wystarczająco różne) naturalne problemy, które dzielą tę właściwość? Sztuczne przykłady pochodzące bezpośrednio z dowodu twierdzenia Ladnera się nie liczą. Czy...
Obecnie jestem studentem, który w tym roku musi ukończyć studia. Po ukończeniu studiów rozważam pracę w kierunku magistra / doktora TCS. Zacząłem się zastanawiać, jakie dziedziny matematyki są uważane za pomocne w TCS, zwłaszcza (klasyczna) teoria złożoności. Jakie dziedziny uważasz za niezbędne...
Matematycy czasem martwią się o aksjomat wyboru (AC) i aksjomat determinacji (AD). Aksjomat wyboru : Biorąc pod uwagę dowolny zbiór z niepustych zestawach jest funkcja , które, biorąc pod uwagę zestaw w , zwraca element z .CC{\cal C}fffSSSCC{\cal C}SSS Aksjomat Determinacji : Niech będzie...
Obecnie rozwiązanie NPNPNP pełnego NP lub PSPACEPSPACEPSPACE jest niewykonalne w ogólnym przypadku dużych nakładów. Jednak oba można rozwiązać w czasie wykładniczym i przestrzeni wielomianowej. Skoro nie jesteśmy w stanie zbudować niedeterministycznych lub „szczęśliwych” komputerów, czy ma to dla...
Znam wiele wyników wykorzystujących twierdzenie PCP (głównie w algorytmach aproksymacyjnych), ale nigdy nie spotkałem się z jasnym wyjaśnieniem twierdzenia PCP (tj. Że ).N P = P C P (O(log( n ) ) , O ( 1 ) )NP=PCP(O(log(n)),O(1))\mathsf{NP} = \mathsf{PCP}(O(\log(n)),O(1)) Jakie są dobre artykuły...
Zadane pytanie dotyczy tego, czy rozstrzygające jest następujące pytanie: Problem Biorąc pod uwagę liczbę całkowitą i maszynę Turinga która ma być w P, to czy środowisko wykonawcze w odniesieniu do długości wejściowej ?M M O ( n k ) nkkkMMMMMM O(nk)O(nk){O}(n^k)nnn Dopuszczalna jest wąska...
Ostatnie pytanie za pytaniem, czy Huck Bennett PH klasa została zawarta w PP klasy, otrzymał nieco sprzecznych odpowiedzi (wszystko prawda, wydaje się). Z jednej strony podano przeciwnie kilka wyników wyroczni, z drugiej Scott zasugerował, że odpowiedź jest prawdopodobnie pozytywna, ponieważ...
Szukam przykładów problemów sparametryzowanych liczbą , gdzie twardość problemu nie jest monotoniczna w k . Z mojego doświadczenia wynika, że większość problemów ma przejście jednofazowe, na przykład k- SAT ma przejście jednofazowe od k ∈ { 1 , 2 } (gdzie problem występuje w P) do k ≥ 3 (gdzie...
Zastanawiam się nad tym pytaniem. Kiedy ludzie opisują problem P vs. NP, często porównują NP klasy do kreatywności. Zauważają, że skomponowanie symfonii jakości Mozarta (analogicznej do zadania NP) wydaje się znacznie trudniejsze niż sprawdzenie, czy już skomponowana symfonia ma jakość Mozarta...
Gdy projektuję algorytm dla nowego problemu, jeśli po pewnym czasie nie mogę znaleźć algorytmu wielomianowego czasu, mogę spróbować udowodnić, że jest to trudny NP. Jeśli mi się uda, wyjaśniłem, dlaczego nie mogłem znaleźć algorytmu czasu wielomianowego. Nie chodzi o to, że wiem na pewno, że P! =...
Natknąłem się na algorytm wielomianowy, który rozwiązuje 2SAT. Uważam za zaskakujące, że 2SAT znajduje się w P, gdzie wszystkie (lub wiele innych) instancji SAT są NP-Complete. Co wyróżnia ten problem? Co sprawia, że jest to takie proste (NL-Complete - nawet łatwiejsze niż...
W złożoności opisowej Immerman ma Wniosek 7.23. Następujące warunki są równoważne: 1. P = NP. 2. Przekroczone, uporządkowane struktury, FO (LFP) = SO. Można to uznać za „wzmocnienie” P = NP do równoważnego wyrażenia w (przypuszczalnie) większych klasach złożoności. Zauważ, że SO...
To moje pierwsze pytanie na tej stronie. Biorę kurs magisterski z teorii obliczeń. Jak wytłumaczysz problem P = NP 10-letniemu dziecku i dlaczego ma on taką nagrodę pieniężną? Twoje zdanie? Zaktualizuję pytanie, gdy moja głowa się o tym
Istnieją pewne problemy z liczeniem, które polegają na zliczaniu wykładniczo wielu rzeczy (w stosunku do wielkości danych wejściowych), a jednak mają zaskakujące algorytmy deterministyczne o czasie wielomianowym. Przykłady obejmują: Zliczanie idealnych dopasowań na wykresie planarnym ( algorytm...
Załóżmy, że i G 2 to dwa niekierowane wykresy na zbiorze wierzchołków { 1 , … , n } . Wykresy są izomorficzne wtedy i tylko wtedy, gdy występuje permutacja Π taka, że G 1 = Π ( G 2 ) lub bardziej formalnie, jeśli istnieje permutacja Π taka, że ( i , j ) jest krawędzią w G 1 wtedy i tylko if ( Π ( i...
W przypadku (wyszukiwania wersji) problemów z NP zakończonych weryfikacja rozwiązania jest wyraźnie łatwiejsza niż znalezienie, ponieważ weryfikacja może być przeprowadzona w czasie wielomianowym, podczas gdy znalezienie świadka zajmuje (prawdopodobnie) wykładniczy czas. Jednak w P rozwiązanie...
To może być pytanie subiektywne, a nie konkretne, ale tak czy inaczej. W teorii złożoności badamy pojęcie wydajnych obliczeń. Istnieją klasy takie jak oznacza czas wielomianowy , a L oznacza miejsce na log . Oba są uważane za reprezentowane jako rodzaj „wydajności” i dość dobrze wychwytują...
Kilka problemów optymalizacyjnych, o których wiadomo, że są trudne do NP na grafach ogólnych, można w prosty sposób rozwiązać w czasie wielomianowym (niektóre nawet w czasie liniowym), gdy grafem wejściowym jest drzewo. Przykłady obejmują minimalną osłonę wierzchołków, maksymalny niezależny zestaw,...
Teoria złożoności jest moim drugorzędnym zainteresowaniem, ale nie jest moim głównym zainteresowaniem badawczym, więc nie mam nadziei, że wezmę udział we wszystkich konferencjach, przeczytam wszystkie blogi i upewnię się, że „w” tłumie cc: ja na każdym gorące wiadomości. Próbuję to zrobić, ale...