Pytania otagowane jako search-problem

1
Złożoność wersji wyszukiwania 2-SAT przy założeniu
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 = NL} Jeśli nie, to co z algorytmami wykorzystującymi przestrzeń sublinearną (w liczbie klauzul)?
4
Najgorsza liczba pytań potrzebna do nauczenia się monotonicznego orzeczenia nad zestawem
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 liczby ocen …
2
Czy algorytm quasiipolomialnego czasu Babai faktycznie generuje izomorfizm?
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 |Gi=(Vi,Ei)Gi=(Vi,Ei)G_i=(V_i,E_i)i∈{1,2}i∈{1,2}i\in\{1,2\}v=|Vi|v=|Vi|v=|V_i| Czy Babai rzeczywiście pokazać , jak …
2
Czy istnienie całkowitego problemu wyszukiwania
Ł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 \mathsf{P}N P.NP\mathsf{NP} Czy odwrotna jest również prawda, tj Czy istnienie …
2
Czy PPAD naprawdę wychwytuje pojęcie znalezienia innego niezrównoważonego wierzchołka?
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 ukierunkowanym występuje niewyważony wierzchołek, musi istnieć inny. Ale zazwyczaj klasa jest …
1
Minimalne elementy monotonicznego predykatu nad zestawem mocy
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 elementy P.PP , tj. x ∈ 2| n |x∈2|n|x \in 2^{|n|}takie, …
1
Znajdź przybliżony argmax, używając tylko przybliżonych maksymalnych zapytań
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 liści odpowiadających indeksom. Zacznij od korzenia i zejdź do liścia w następujący sposób. W każdym węźle zapytaj …
1
Czy losowa wyrocznia może zmienić, które problemy TFNP są średnio trudne?
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 formalnie, RRR \newcommand{\Pr}{\operatorname{Pr}} \newcommand{\E}{\operatorname{\mathbb{E}}} \newcommand{\O}{\mathcal{O}} \newcommand{\Good}{\mathsf{Good}} Robi dla wszystkich algorytmów P / poli , \ …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.