Pytania dotyczące twardości NP i kompletności NP.
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 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...
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...
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ż...
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,...
Książka Arory i Baraka przedstawia faktoring jako następujący problem: FACTORING={⟨L,U,N⟩|(∃ a prime p∈{L,…,U})[p|N]}FACTORING={⟨L,U,N⟩|(∃ a prime p∈{L,…,U})[p|N]}\text{FACTORING} = \{\langle L, U, N \rangle \;|\; (\exists \text{ a prime } p \in \{L, \ldots, U\})[p | N]\} Dodają, w dalszej części...
Mam na myśli następujący problem: Chcę znaleźć wyrażenie regularne, które pasuje do określonego zestawu ciągów (np. Prawidłowe adresy e-mail) i nie pasuje do innych (nieprawidłowe adresy e-mail). Załóżmy, że przez wyrażenie regularne rozumiemy dobrze zdefiniowaną maszynę skończoną, nie znam...
To jest cross-post z math.stackexchange. Niech FACT oznaczają problemu faktoringowej całkowitą: podany znaleźć liczb pierwszych p i ∈ N , a całkowite e I ∈ N , tak, że N = Π k i = 0 p e ı ı .n∈N,n∈N,n \in \mathbb{N},pi∈N,pi∈N,p_i \in \mathbb{N},ei∈N,ei∈N,e_i \in...
Dlaczego większość ludzi woli stosować redukcje wielokrotne jeden do zdefiniowania kompletności NP zamiast, na przykład, redukcji
Biorąc pod uwagę nowy problem w którego prawdziwa złożoność jest gdzieś pomiędzy P a ukończeniem NP, istnieją dwie metody, o których wiem, że mogą być wykorzystane do udowodnienia, że rozwiązanie tego jest trudne:N P.N.P.\mathsf{NP}P.P.\mathsf{P} Pokaż, że problem dotyczy GI (GI = Graph...
Mark Dominus zebrał kilka przykładów redukcji czasu wielomianowego od różnych trudnych problemów NP do dopasowania „wyrażenia regularnego” . Wyobrażanie sobie weryfikacji w czasie wielomianowym nie jest ogromnym skokiem. Jak zilustrujesz klasę NP-zupełną studentom lub przyjaciołom z innych...
Mam pytanie historyczne. Próbuję ustalić odniesienie dla faktu, że 3-kolorowalność grafów (alternatywnie, kolorowalność dla danego k ≥ 3 ) jest NP-trudna.kkkk ≥ 3k≥3k\geq 3 Kuszącą odpowiedzią jest „oryginał Karpa”, ale to nieprawda. Oto skan: Reducibility Among Combinatorial Problems, Karp...
Dowolną liczbę naturalną można traktować jako sekwencję bitową, więc wprowadzenie liczby naturalnej jest takie samo, jak wprowadzenie sekwencji 0-1, więc oczywiście występują problemy NP-zupełne z wejściami naturalnymi. Ale czy są jakieś naturalne problemy, tzn. Takie, które nie używają kodowania i...
Niech oznacza problem (decyzji) w NP, a # oznacza jego wersję zliczającą.XXXXXXX Pod jakimi warunkami wiadomo, że „X to NP-zupełny” że „X jest kompletny?⟹⟹\implies Oczywiście istnienie skąpej redukcji jest jednym z takich warunków, ale jest to oczywiste i jedyny taki warunek, o którym wiem....
Były dwa pytania zadawane niedawno na cs.se które były albo spokrewnione lub miał szczególny przypadek równoznaczne z następującym pytaniem: Załóżmy, że masz ciąg a1,a2,…ana1,a2,…ana_1, a_2, \ldots a_n z nnn liczb takich, że Rozłóż go na sumę dwóch permutacji, i , z , tak...
Czy ma sens rozważenie kategorii wszystkich problemów związanych z NP-zupełnością, z morfizmami jako redukcjami wielomianów między różnymi instancjami? Czy ktoś kiedykolwiek opublikował artykuł na ten temat, a jeśli tak, to gdzie mogę go
Wiemy, że (patrz np. Twierdzenia 1 i 3 z [1]), z grubsza mówiąc, w odpowiednich warunkach, funkcje, które mogą być skutecznie obliczone przez maszynę Turinga w czasie wielomianowym („wydajnie obliczalne”), mogą być wyrażone przez wielomianowe sieci neuronowe z rozsądnymi rozmiarami, a zatem można...
Czytając artykuł „Czy nadszedł czas, aby zadeklarować zwycięstwo w liczeniu złożoności?” na blogu „Godel's Lost Letter and P = NP” wspominali o dychotomii CSP. Po kilku linkach, googlowaniu i wikipedii natknąłem się na twierdzenie Ladnera : Twierdzenie Ladnera: jeśli , wówczas występują problemy...
Uważam ten artykuł za bardzo interesujący. Podsumowując: omawia, dlaczego w praktyce rzadko znajduje się najgorszy przypadek problemu NP-zupełnego. Idea tego artykułu polega na tym, że przypadki są zwykle bardzo niedostatecznie lub bardzo przeciążone, a oba są stosunkowo łatwe do rozwiązania....