Pytania otagowane jako cc.complexity-theory

P a NP i inne obliczenia ograniczone do zasobów.

1
Nieprawidłowe płaskie ubarwienie o wielkości elementu monochromatycznego
Rozluźnijmy trochę kolorystykę, tzn. Pozwalamy niewielkiej liczbie sąsiadujących wierzchołków na przypisanie tego samego koloru. Składnik monochromatyczny jest zdefiniowany jako składnik połączony w podsgrafie wywołany przez zestaw wierzchołków, które otrzymują ten sam kolor, a pytanie polega na zapytaniu o minimalną liczbę kolorów potrzebną do pokolorowania wykresu, tak aby największy składnik monochromatyczny …
1
Redundancja i struktura problemów obliczeniowych
Powszechnie uważa się, że niektóre problemy obliczeniowe, takie jak izomorfizm grafów, nie mogą być NP-kompletne, ponieważ nie mają wystarczającej struktury lub redundancji, aby były trudne obliczeniowo (NP-twarde). Interesują mnie różne pojęcia formalne dotyczące struktury problemów obliczeniowych i miar redundancji. Jakie są główne znane wyniki takich formalnych pojęć dotyczących problemów obliczeniowych? …
1
Mechanizm dostępu do wyroczni Ruzzo-Simon-Tompa
W artykule na temat relatywizacji obliczeń przestrzeni logicznej Ladner i Lynch konstruują wyrocznię, do której . W literaturze można znaleźć więcej patologicznych przykładów. Czytałem kilka artykułów na temat relatywizowanych małych klas kosmicznych, a jednym z podstawowych narzędzi w tym obszarze jest mechanizm dostępu do wyroczni Ruzzo-Simon-Tompa (RST), który wymaga deterministycznej, …
2
Warianty bezpośrednich twierdzeń o produktach
Bezpośrednie twierdzenie o produkcie, nieformalnie, mówi, że obliczenie instancji funkcji f jest trudniejsze niż jednorazowe obliczenie f .kkkfafffaff Typowe bezpośrednie twierdzenia o produktach (np. XOR Lemma Yao) patrzą na złożoność średnich przypadków i twierdzą (bardzo z grubsza), że nie może być obliczone przez obwody o wielkości s z prawdopodobieństwem większym …
2
Czy problem znalezienia operatorów spełniających listę zmiennych boolowskich NP jest kompletny?
Jest to podobne do SAT, z tym wyjątkiem, że znamy przypisanie każdej zmiennej, ale nie znamy przypisania żadnego operatora logicznego. Czy w takim przypadku znalezienie przypisania każdego operatora, aby wyrażenie oceniało na wartość logiczną, stanowi problem NPC? Właściwie zastanawiałem się, czy znalezienie przypisania operatorów arytmetycznych w celu spełnienia liczby całkowitej …
1
Dolne granice uczenia się w zapytaniu o członkostwo i modelu kontrprzykładowym
Dana Angluin ( 1987 ; pdf ) definiuje model uczenia się z zapytaniami o członkostwo i teoriami (kontrprzykłady do proponowanej funkcji). Pokazuje, że zwykły język reprezentowany przez minimalny DFA z stanów jest możliwy do nauczenia się w czasie wielomianowym (gdzie proponowane funkcje to DFA) z zapytaniami o członkostwo i co …
3
Czy P zawiera niezrozumiałe języki? (Wiki społeczności TCS)
Odpowiedź: nieznana Ogromne podziękowania dla wszystkich, którzy pomogli dopracować to pytanie i związane z nim definicje. Definicje tej wiki stanowiły punkt wyjścia dla najnowszej wiki TCS „ Czy P zawiera języki, których istnienie jest niezależne od PA lub ZFC? (Wiki społeczności TCS) ”. Preferowana jest nowsza wiki, ponieważ jej definicje …
1
Optymalne przetwarzanie wstępne dla niektórych rodzajów zapytań
Załóżmy, że mamy półgrupę z elementami . Naszym celem jest obliczanie produktów .(S,∘)(S,∘)(S,\circ)S={s1,s2,…,sn}S={s1,s2,…,sn}S=\lbrace s_1,s_2,\dots,s_n\rbracesi∘si+1∘⋯∘sjsi∘si+1∘⋯∘sjs_i\circ s_{i+1}\circ \cdots\circ s_j W swoim artykule „Optymalne przetwarzanie wstępne dla odpowiedzi na zapytania produktów on-line” Alon i Schieber udowadniają, że możemy odpowiedzieć na każde takie zapytanie w co najwyżej krokach (gdzie jest odwrotną funkcją Ackermanna), używając …
3
Wydajne porównanie DAG przez sieć
W rozproszonych systemach kontroli wersji (takich jak Mercurial i Git ) istnieje potrzeba skutecznego porównywania ukierunkowanych wykresów acyklicznych (DAG). Jestem programistą Mercurial i bardzo chcielibyśmy usłyszeć o pracy teoretycznej, która omawia złożoność czasową i sieciową porównywania dwóch DAG. Wspomniane DAG są tworzone na podstawie zarejestrowanych zmian. Wersje są jednoznacznie identyfikowane …
1
Jaka jest złożoność obliczania liczby rozwiązań problemu P-Space Complete? Co powiesz na klasy o wyższej złożoności?
Chyba nazywa się to # P-Space, ale znalazłem tylko jeden artykuł niejasno o tym wspominając. Co powiesz na liczącą się wersję problemów EXP-TIME-Complete, NEXP-Complete oraz EXP-SPACE-Complete? Czy są jakieś wcześniejsze prace, które można przytoczyć w odniesieniu do tego lub dowolnego rodzaju włączenia lub wyłączenia, takiego jak Toda's Torem?
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.