Kilka lat temu była praca Joela Friedmana związana z dolnymi granicami obwodu z kohomologią Grothendiecka (patrz dokumenty: http://arxiv.org/abs/cs/0512008 , http://arxiv.org/abs/cs/0604024 ). Czy ten sposób myślenia przyniósł jakieś nowe spojrzenie na złożoność logiczną, czy pozostaje raczej...
Jako amator TCS czytam popularny materiał wprowadzający na temat komputerów kwantowych. Oto kilka podstawowych elementów informacji, których nauczyłem się do tej pory: Komputery kwantowe nie są znane z rozwiązywania problemów NP-zupełnych w czasie wielomianowym. „Magia kwantowa nie wystarczy”...
Zdefiniuj LOGLOG jako klasę języków, które mogą być obliczane w przestrzeni O (loglog n) przez deterministyczną maszynę Turinga (z dwukierunkowym dostępem do danych wejściowych). Podobnie zdefiniuj NLOGLOG jako klasę języków, które mogą być obliczane w przestrzeni O (log log n) przez...
Często cytowane jest filozoficzne uzasadnienie, by wierzyć, że P! = NP nawet bez dowodu. Inne klasy złożoności mają dowody na ich odrębność, ponieważ jeśli nie, miałyby „zaskakujące” konsekwencje (takie jak upadek hierarchii wielomianowej). Moje pytanie brzmi: jaka jest podstawa przekonania, że...
Niemożliwe jest napisanie języka programowania, który zezwala wszystkim maszynom, które zatrzymują się na wszystkich wejściach i żadnych innych. Wydaje się jednak, że łatwo jest zdefiniować taki język programowania dla dowolnej standardowej klasy złożoności. W szczególności możemy zdefiniować...
W tym pytaniu formuła 3CNF oznacza formułę CNF, w której każda klauzula obejmuje dokładnie trzy różne zmienne. Dla stałych 0 < s <1, Gap-3SAT s stanowi następujący problem: GAP 3SAT s wystąpienia : a 3CNF wzór φ. Tak, obietnica : φ jest satysfakcjonująca. No-obietnica : Brak przypisania...
W artykule Losowa hipoteza Oracle jest fałszywa , autorzy (Chang, Chor, Goldreich, Hartmanis, Håstad, Ranjan i Rohatgi) omawiają implikacje hipotezy losowo-wyroczni . Twierdzą, że niewiele wiemy o separacjach między klasami złożoności, a większość wyników wymaga albo przyjęcia rozsądnych założeń,...
To pytanie dotyczy problemów, dla których istnieje duża otwarta luka złożoności między znaną dolną i górną granicą, ale nie z powodu otwartych problemów dotyczących samych klas złożoności. Mówiąc ściślej, powiedzmy, że problem ma klasy przerw (z A ⊆ B , nie jednoznacznie zdefiniowane), jeśli A...
Wokół jest mnóstwo problemów z kompletnym NP i źródła je zbierające, np. Patrz książka Garey i Johnsona. Byłbym również zainteresowany, aby zobaczyć listę problemów uzupełniających NEXP. Czy jest dostępny? Ponieważ zakładam, że nie ma, otwieram to pytanie (czy to ma być wiki społeczności? Nie wiem...
Łączność ST to problem polegający na określeniu, czy istnieje ukierunkowana ścieżka między dwoma wyróżnionymi wierzchołkami i t na ukierunkowanym wykresie G ( V , E ) . To, czy problem ten można rozwiązać w przestrzeni logów, jest od dawna otwartym problemem. Jest to tak zwany N l vs L...
W tym poście Josh Grochow na blogu o złożoności relacjonuje ostatnie warsztaty poświęcone GCT, które odbyły się w lipcu w Princeton. Kilku uczestników argumentowało, że powinniśmy używać GCT do atakowania łatwiejszych problemów niż PP.\mathsf{P} vs. NPN.P.\mathsf{NP} w celu zbudowania intuicji i...
Decydowanie, czy skwantyfikowana formuła boolowska, taka jak ∀ x1∃ x2)∀ x3)⋯ ∃ xnφ ( x1, x2), … , Xn) ,∀x1∃x2∀x3⋯∃xnφ(x1,x2,…,xn),\forall x_1 \exists x_2 \forall x_3\cdots \exists x_n \varphi(x_1, x_2,\ldots , x_n), zawsze ocenia na prawdę, to klasyczny problem z PSPACE. Można to postrzegać jako...
Byłem (i nadal jestem) bardzo zainteresowany odpowiedzią na to pytanie, ponieważ jest to interesująca odmiana złożoności gier, która nie została jeszcze rozwiązana, więc zaoferowałem nagrodę. Pomyślałem, że pierwotne pytanie jest prawdopodobnie zbyt trudne, więc zamieściłem trzy powiązane pytania,...
Pozwolić L={n:the nth binary digit of π is 1}L={n:the nth binary digit of π is 1}L = \{ n : \text{the }n^{th}\text{ binary digit of }\pi\text{ is }1 \} (gdzie jest uważane za zakodowane w systemie binarnym). Co zatem możemy powiedzieć o złożoności obliczeniowej ? Oczywiste jest, że . I jeśli się...
Pomyślałem, że podzielę się tym pytaniem, ponieważ może być interesujące dla innych użytkowników tutaj. Załóżmy, że funkcja, która jest klasą jednolitej (jak ) jest także w niewielkim klasy nierównomierne (jak A C 0 / P O l y , czyli niejednolity C 0 ), czy to oznacza, że funkcja ta jest zawarta w...
Zakładając, że P! = NP, uważam, że wykazano, że istnieją problemy, których nie ma w P, a nie w NP-Complete. Przypuszcza się, że takim problemem jest izomorfizm grafów. Czy są jakieś dowody na istnienie większej liczby takich „warstw” w NP? tzn. Hierarchia złożona z więcej niż trzech klas,...
Chciałbym znaleźć algorytm wielomianowy, który określa, czy rozpiętość danego zestawu macierzy zawiera macierz permutacji. Jeśli ktoś wie, czy ten problem ma inną klasę złożoności, byłoby to równie pomocne. EDYCJA: Oznacziłem to pytanie za pomocą programowania liniowego, ponieważ mam poważne...
Jeśli spojrzymy na twierdzenie o hierarchii DTIME, mamy dziennik z powodu narzutu w symulacji deterministycznej maszyny Turinga przez maszynę uniwersalną: DTIME(flogf)⊊DTIME(f)DTIME(flogf)⊊DTIME(f)DTIME(\frac{f}{\log f}) \subsetneq DTIME(f) Nie mamy tego rodzaju kosztów ogólnych dla NTIME...
Zdefiniuj ioioio - jako klasę języków taką, że istnieje język i dla nieskończenie wielu , i zgadzają się we wszystkich przypadkach długości n . (To jest klasa języków, które można „rozwiązywać nieskończenie często, w podwykonawczym czasie”).SUBEXPSUBEXPSUBEXPL ′ ∈ ∩ ε >...
Cytując Wikipedię , „[Gra życia Conwaya] ma moc uniwersalnej maszyny Turinga: to znaczy wszystko, co można obliczyć algorytmicznie, można obliczyć w ramach Gry życia Conwaya”. Czy takie wyniki obejmują hałaśliwe wersje Gry życia Conwaya? Najprostsza wersja jest taka, że po każdej rundzie każda...