Załóżmy, że mam poset „S” i monotoniczny predykat „P” na S. Chcę znaleźć jeden lub wszystkie maksymalne elementy S spełniające P. EDIT : Jestem zainteresowany minimalizując liczbę ocen P . Jakie algorytmy istnieją dla tego problemu i jakich właściwości i dodatkowych operacji wymagają na S? Co z...
W „Obliczeniach kwantowych i informacjach kwantowych” Mike'a i Ike'a algorytm Grovera został szczegółowo wyjaśniony. Jednak w książce i we wszystkich wyjaśnieniach, które znalazłem w Internecie dla algorytmu Grovera, wydaje się, że nie ma wzmianki o tym, jak zbudowana jest Wyrocznia Grovera, chyba...
Rozważmy skończoną posetę ponad elementów, a nieznany monotoniczny predykat nad (tj. Dla dowolnego , , jeśli i to ) . Mogę ocenić , podając jeden węzeł i sprawdzając, czy utrzymuje, czy nie. Moim celem jest określenie dokładnie zestawu węzłów tak, że P (x) utrzymuje, przy użyciu jak najmniejszej...
Jeśli , a następnie jest algorytm logspace który rozwiązuje wersja decyzja 2-SAT.L=NLL=NL\mathsf{L = NL} Czy wiadomo, że sugeruje, że istnieje algorytm przestrzeni logicznej, który pozwala uzyskać zadowalające przypisanie , jeśli dane wejściowe są zadowalające dla 2-SAT?L=NLL=NL\mathsf{L =...
Czytałem artykuł na Wikipedii o problemie ośmiu królowych. Stwierdzono, że nie ma znanego wzoru na dokładną liczbę rozwiązań. Po kilku poszukiwaniach znalazłem artykuł o twardości liczenia problemów z kompletnymi mapowaniami. W tym artykule jest problem, który okazuje się co najwyżej tak trudny jak...
Łatwo zauważyć, że jeśli to istnieją całkowite N P problemy wyszukiwania, których nie można rozwiązać w czasie wielomianowym (stwórz całkowity problem wyszukiwania, mając zarówno świadków członkostwa, jak i świadków braku członkostwa).N P ∩ c o N P ≠ PNP∩coNP≠P\mathsf{NP}\cap\mathsf{coNP} \neq...
Klasa złożoności PPAD została wynaleziona przez Christosa Papadimitriou w jego przełomowym artykule z 1994 roku . Klasa ma na celu uchwycenie złożoności problemów wyszukiwania, w których istnienie rozwiązania jest gwarantowane przez „Argument parzystości w grafach ukierunkowanych”: jeśli w grafie...
Mam (mam nadzieję, że proste, może głupie) pytanie na przełomowy artykuł Babai, który pokazuje, że jest quasipolynomial.GIGI\mathsf{GI} Babai pokazał, jak stworzyć certyfikat, że dwa wykresy dla są izomorficzne, z czasem quasipolynomial in.i ∈ { 1 , 2 } v = | V i
Rozważ monotoniczny predykat PPP nad zestawem mocy 2|n|2|n|2^{|n|}(uporządkowane przez włączenie). Przez „monotoniczny” rozumiem: ∀x,y∈2|n|∀x,y∈2|n|\forall x, y \in 2^{|n|}tak, że x ⊂ yx⊂yx \subset y , jeśli P.( x )P(x)P(x) to P.( y)P(y)P(y) . Szukam algorytmu, aby znaleźć wszystkie minimalne...
Rozważ następujący problem. nnnv1,⋯,vn∈Rv1,⋯,vn∈Rv_1, \cdots, v_n \in \mathbb{R}S⊆{1,⋯,n}S⊆{1,⋯,n}S \subseteq \{1,\cdots,n\}maxi∈Svimaxi∈Svi\max_{i \in S} v_i Ten problem jest prosty: możemy użyć wyszukiwania binarnego, aby znaleźć argmax z zapytaniami . tj. Zbuduj kompletne drzewo binarne z...
Zastanawiałem się nad następującym pytaniem w różnych momentach, odkąd widziałem to pytanie w kryptografii . Pytanie Pozwolić RRRbyć relacją TFNP . Czy losowa wyrocznia może pomóc P / poli w przełamaniu z nieistotnym prawdopodobieństwem? Bardziej