Jestem głównym matematykiem zainteresowanym TCS. Chcę samemu przestudiować algorytmy i ich złożoność w celu rozwiązania grupowych problemów teoretycznych, takich jak znajdowanie porządku elementów, wyliczanie zbioru, wyszukiwanie generatora, testowanie, czy dany podzbiór generuje grupę. Jaką...
Możemy myśleć o złożoności łańcucha Kołmogorowa jako długości najkrótszego programu P i wprowadzić y tak, że x = P ( y ) . Zazwyczaj programy te są pobierane z jakiegoś kompletnego zestawu Turinga (np. P może być opisem maszyny Turinga lub może to być program w LISP lub C). Nawet gdy patrzymy na...
Jeśli jest wykresem w stopniu maksymalnie 3 i jest minor H , a G jest topologiczna minor H .solGGH.HHsolGGH.HH Wikipedia cytuje ten wynik z „Teorii grafów” Diestela. Jest wymieniony jako Prop 1.7.4 w najnowszej wersji książki. W książce brakuje dowodu lub cytowania. Czy miejsce pobytu znane jest...
Odpowiadając na to pytanie w cstheory , (nieformalnie) udowodniłem w locie następujące twierdzenie: Twierdzenie : Dla dowolnego ustalonego sonda cyklu Hamiltoniana pozostaje NP-kompletna, nawet jeśli jest ograniczona do płaskich dwustronnych grafów niekierowanych o maksymalnym stopniu 3, które nie...
Szukam pracy ankietowej na temat ważnych pojęć w dziedzinie automatów kwantowych. Znalazłem teorię automatów kwantowych - recenzję Hirvensalo, ale brzmi to zbyt zwięźle, by zrozumieć ten temat. Czy istnieje dość kompleksowa ankieta na temat automatów kwantowych? Czy mógłbyś również wskazać mi...
Powiedzmy, że wykres ma właściwość M, jeśli jego wierzchołki można uporządkować v 1 , v 2 , … v n w taki sposób, że wykres H i indukowany przez wierzchołki { v 1 , … , v i } ma d i s t H i ( v j , v k ) = d i s t G ( v j , vsolGGM.MMv1, v2), … Vnv1,v2,…vnv_1, v_2, \ldots v_nH.jaHiH_i{ v1, … ,...
Unikalny SAT jest dobrze znanym problemem: biorąc pod uwagę wzór CNF , czy to prawda, że F ma dokładnie jeden model?FFFFFF Interesuje mnie problem «Dokładnie SAT»: biorąc pod uwagę wzór F CNF i liczbę całkowitą m > 1 , czy to prawda, że F ma dokładnie m modeli?mmmFFFm>1m>1m>1FFFmmm Oba...
Kto jako pierwszy pokazał, że dany język jest w NP, jeśli certyfikat dla tego języka można zweryfikować w czasie wielomianowym? Czy mamy dokument, który formalnie to potwierdza? Kiedy społeczność TCS zaczęła kłaść nacisk na niedeterminizm na rzecz weryfikowalności? Nie mogę znaleźć dla tego dobrego...
Więc wszyscy znamy dolną granicę drzewa na podstawie najgorszego przypadku porównań wykonanych przez (deterministyczny) algorytm sortowania porównań. Nie dotyczy losowego sortowania porównań (jeśli mierzymy oczekiwane porównania dla danych wejściowych w najgorszym przypadku). Na przykład, dla ,...
Jaka jest minimalna szerokość drzewa obwodu powyżej {∧,∨,¬}{∧,∨,¬}\{\wedge,\vee,\neg\} do obliczenia MAJ? Tutaj MAJ :{0,1}n→{0,1}:{0,1}n→{0,1}:\{0,1\}^n \rightarrow \{0,1\} wyprowadza 1, jeśli co najmniej połowa jego danych wejściowych to 111 . Dbam tylko o rozmiar obwodu (powinien być...
Szukam odniesień bibliograficznych dla następującego algorytmu / problemu: nazwałem go „BiSelect” lub „t-ary Select” lub „Select in Union of Sorted Arrays”, ale myślę, że został wprowadzony wcześniej pod inną nazwą? Problem Rozważ następujący problem: Biorąc pod uwagę kkk rozłożonych tablic...
Jestem pewien, że nie jako pierwszy rozważyłem pomysł, który zamierzam przedstawić. Przydałoby się jednak znalezienie literatury związanej z tym pomysłem. Chodzi o to, aby zbudować Maszynę Turinga M z właściwością, że jeśli P = NP, wówczas M rozwiąże 3-SAT w czasie wielomianowym. (Wybór 3-SAT jest...
Mam nadzieję, że ktoś wie o tym, więc nie muszę czytać literatury ... Rozważ ciąg liczb . Pomyśl o sekwencji jako interwałach . Oczywiście, oryginalna sekwencja jest bitoniczna, jeśli jakikolwiek punkt na prawdziwej linii dźgnie co najwyżej 2 interwały. Będziemy odnosić się do sekwencji, w której...
MPA (automat multipebble) to 2DFA (dwukierunkowy deterministyczny automat skończony), który może wykorzystywać dowolną liczbę otoczek (w rzeczywistości najwyżej otoczki na danym wejściu - wejście jest zapisywane na taśmie między dwoma końcami -markery jak ). Podczas obliczeń MPA może wykryć, czy...
Czytam ankiety Trevisana i Lovetta dotyczące zastosowań dodatku kombinatorycznego w TCS. Większość tych aplikacji ma złożoność obliczeniową , np. Niższe granice. Zastanawiam się, czy kombinatoryka addytywna znalazła również zastosowania w projektowaniu algorytmów . Motywacja mojego pytania jest...
Jeśli otrzymujesz zbiór zamówień częściowych, sortowanie topologiczne powie ci, czy istnieje rozszerzenie zbioru do zamówienia całkowitego (w tym przypadku rozszerzenie jest zamówieniem całkowitym zgodnym z każdym z zamówień częściowych). Natknąłem się na odmianę: Naprawić zestaw . Dostajesz...
Szybkie wyszukiwanie w Internecie doprowadziło mnie do przekonania, że „APXHardness implikuje, że nie ma QPTAS dla problemu, chyba że [jakaś klasa złożoności] jest zawarta w [innej klasie złożoności]” i jest również dobrze znana! Wygląda na to, że wszyscy o tym wiedzą oprócz mnie. Niestety nie...
Algorytm simpleksowy jest często traktowany albo w ramach rzeczywistej arytmetyki, albo w świecie dyskretnym z dokładnymi obliczeniami. Wydaje się jednak, że jest najczęściej wdrażany za pomocą arytmetyki zmiennoprzecinkowej. Prowadzi to do pytania, czy algorytm simpleks należy traktować jako...
Czy wiemy, że hierarchia się nie zwija ( dla wszystkich d )?TC0TC0\mathsf{TC^0}TC0d⊊TC0d+1TCd0⊊TCd+10\mathsf{TC^0_d} \subsetneq \mathsf{TC^0_{d+1}}ddd Wpis do zoo dla TC0TC0\mathsf{TC^0} wspomina tylko o separacji między głębokością 2 i 3. Czy istnieje również standardowe odniesienie do faktu, że...
Obecnie prowadzę badania nad językiem formalnym, które obejmują klasy języków powyżej zwykłego, ale poniżej kontekstowego. Patrzę na takie rzeczy, jak maszyny zliczające z odwróceniem, maszyny liczące na jednym stosie, deterministyczne CFL itp. Zastanawiam się, czy ktokolwiek wie o dobrej książce...