Próbuję znaleźć problemy, których złożoność przestrzeni dla średnich przypadków została przeanalizowana. Mówiąc dokładniej, jestem zainteresowany, aby dowiedzieć się, czy są jakieś problemy ze sprawdzoną dolną granicą złożoności przestrzeni, która jest superliniowa, a zwłaszcza, jeśli istnieją...
Nurikabe to układanka wypełniająca siatki oparta na ograniczeniach, luźno podobna do Saperów / Nonogramów; liczby są umieszczane na siatce, która ma być wypełniona wartościami włączania / wyłączania dla każdej komórki, przy czym każda liczba wskazuje region połączonych komórek „on” o tej wielkości,...
Mam problem, który jest w NEXP NP i który może być rozwiązany przez przemienną TM przy użyciu czasu wykładniczego i tylko jednej alternacji (zaczynając od stanu egzystencjalnego).NPNP^{\text{NP}} Czy jest coś znanego na temat NEXP NP ? Czy jest równy NEXP lub innej klasie? Czy istnieją inne...
Kompletność i solidność w interaktywnych systemach dowodowych są nieformalnie definiowane jako: Kompletność: Jeśli stwierdzenie jest prawdziwe, szczery Prover może przekonać uczciwego weryfikatorem tego faktu WHP . Poprawność: jeśli oświadczenie jest fałszywe, oszust nie może przekonać uczciwego...
Nie pamiętam, że widziałem separację klas nieopartą na wynikach diagonalizacji i relatywizacji. Diagonalizacja może być nadal używana do oddzielania pozostałych znanych klas, ponieważ argumenty nierelatywizujące mogą być nadal stosowane w konkluzji o diagonalizacji lub w konstrukcji...
W 1975 r. Miller pokazał, jak zmniejszyć faktoryzację liczby całkowitej do znalezienia okresu r funkcji f ( x ) = a xN.NNrrr taki, że f ( x + r ) = f ( x ) z niektórymi losowo wybranymi a < N . Dobrze wiadomo, że algorytm Shora możeefektywnieznajdować r na komputerze kwantowym, podczas gdy uważa...
Co wiadomo na temat przejścia fazowego w problemach # P-Complete? W szczególności, czy istnieje inne przejście fazowe dla # DNF-k-SAT i # CNF-k-SAT? Aktualizacja: Jak wiemy, w Random k-SAT występuje przejście fazowe, w którym rozwiązanie problemu staje się łatwe i trudne. Chciałbym również...
Jak spojrzeć na problem i powód, dla którego jest to NP-średniozaawansowany, a nie NP-pełny? Często dość łatwo jest spojrzeć na problem i stwierdzić, czy jest to prawdopodobnie NP-Complete, czy nie, ale wydaje mi się, że znacznie trudniej jest stwierdzić, czy problem dotyczy NP-Intermediate,...
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...
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...
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...
Czy istnieją problemy, których średnia złożoność przypadków jest taka sama jak ich najgorsza złożoność? Jakie są podstawowe właściwości tych problemów, które pozwalają zredukować najgorszy przypadek do przeciętnego
Interesuje mnie odmiana SAT, w której wzór CNF jest monotoniczny (żadnych zmiennych nie neguje się). Taka formuła jest oczywiście zadowalająca. Ale powiedzmy, że liczba prawdziwych zmiennych jest miarą tego, jak dobre jest nasze rozwiązanie. Mamy więc następujący problem: MINIMALNY PRAWDZIWY...
To pytanie może nie mieć charakteru technicznego. Jako nie-native speaker i TA dla klasy algorytmów zawsze zastanawiałem się, co oznacza gadżet w „gadżet klauzulowy” lub „gadżet zmienny”. Słownik mówi, że gadżet jest maszyną lub urządzeniem, ale nie jestem pewien, co to kolokwialne znaczenie ma w...
Pracuję w obliczeniowym laboratorium neuronauki, które ocenia ilościowo wzajemną informację między parami lub grupami neuronów. Ostatnio szef skupił się na pomiarze „złożoności dynamiki neuronowej”. Prowadząc tę linię badań, niektórzy ludzie w mojej grupie wydają się utożsamiać „kompleks” z „ma...
Problem podziału na 3 kliki polega na określeniu, czy wierzchołki wykresu, powiedzmy , można podzielić na 3 kliki. Problem ten jest trudny do wyeliminowania przez proste zmniejszenie z 3-kolorowego problemu. Nietrudno dostrzec, że odpowiedź na ten problem jest łatwa, gdy diam ( G ) = 1 lub diam ( G...
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...
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...
W artykule „Programowanie liczb całkowitych ze stałą liczbą zmiennych” wykazano, że programowanie liczb całkowitych o stałej liczbie ograniczeń (lub zmiennych) można rozwiązać wielomianowo. Czy to dotyczy programowania
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) ”....