Próbuję zrozumieć artykuł na temat p-Optimal Proof Systems and Logic for PTIME . W artykule jest pojęcie nazywane systemami dowodowymi i nie rozumiem intencji: Σ = { 0 , 1 }Σ={0,1}\Sigma = \{0,1\} ... Identyfikujemy problemy z podzbiorami w .QQQΣ∗Σ∗\Sigma^* Myślę, że intencją jest to, że...
Aby lepiej zrozumieć artykuł, staram się krótko zrozumieć logikę najmniej ustalonego punktu. Utknąłem w kilku punktach. Gdyby G = ( V, E)G=(V,E)G = (V,E) jest wykresem i Φ ( str) = { ( a , b ) ∣ G ⊨ E( a , b ) ∨ P( a , b ) ∨ ∃ z( E( a , z) ∧ P( z, b ) )
W artykule Adi Shamira [1] z 1979 r. Pokazuje, że faktoring można wykonać w wielomianowej liczbie kroków arytmetycznych . Fakt ten został powtórzony i dlatego zwrócił moją uwagę w niedawnej pracy Borweina i Hobarta [2] w kontekście programów liniowych (SLP). Ponieważ byłem raczej zaskoczony, gdy...
Pozwolić ATISP(f(n),g(n))ATISP(f(n),g(n))\mathsf{ATISP}(f(n), g(n)) być klasą języków ustaloną przez naprzemienne maszyny Turinga, które zatrzymują się w czasie f(n)f(n)f(n) używając przestrzeni g(n)g(n)g(n). PozwolićAALTSP(f(n),g(n))AALTSP(f(n),g(n))\mathsf{AALTSP}(f(n), g(n)) być klasą języków...
Jestem zmieszany. Chcę udowodnić, że problem sortowania macierzy przez , tj. Wiersze i kolumny są w porządku rosnącym, to . Kontynuuję, zakładając, że można to zrobić szybciej niż i próbuję złamać dolną granicę Dla porównań potrzebnych do posortowania m elementów. Mam dwie sprzeczne...
Zamknięte. To pytanie jest nie na temat . Obecnie nie przyjmuje odpowiedzi. Chcesz poprawić to pytanie? Zaktualizuj pytanie, aby było tematem wymiany stosów teoretycznych w informatyce. Zamknięte 7 lat temu . Jak możemy wyrazić „ ” jako formułę...
Załóżmy, że działamy w polu skończonym. Otrzymujemy duży stały wielomian p (x) (powiedzmy stopnia 1000) nad tym polem. Ten wielomian jest znany wcześniej i możemy wykonywać obliczenia przy użyciu dużej ilości zasobów w „fazie początkowej”. Wyniki te mogą być przechowywane w stosunkowo małych...
Rozważ formułę Monotone 3CNF mającą oba następujące dodatkowe ograniczenia: Każda zmienna występuje dokładnie w klauzulach.2)22 Biorąc pod uwagę dowolne klauzule, mają one maksymalnie zmienną.2)22111 Chciałbym wiedzieć, jak ciężko jest liczyć satysfakcjonujące zadania takiej...
Pozwolić faFF być rodziną redd-elementowe podzbiory skończonego wszechświata UUUprzedmiotów. RodzinaH.HH z kkkpodzbiory elementów UUU, z 1 ≤ k < d1≤k<d1 \le k < d, jest ( k , d)(k,d)(k,d)- trafienie ustawione odfaFF jeśli dla każdego V.∈ F.V∈FV \in F istnieje co najmniej jeden zestaw W∈HW∈HW...
Algorytm Berkowitza zapewnia obwód wielomianowy o głębokości logarytmicznej do wyznaczania macierzy kwadratowej z wykorzystaniem mocy macierzy. Algorytm domyślnie wykorzystuje anulowanie. Czy anulowanie jest niezbędne do uzyskania obwodu wielomianowego o głębokości logarytmicznej lub liniowej w...
Pozwolić xi∈{−1,0,+1}xi∈{−1,0,+1}x_i \in \{-1,0,+1\} dla i∈{1,…,n}i∈{1,…,n}i \in \{1,\ldots,n\}, z obietnicą, że x=∑ni=1xi∈{0,1}x=∑i=1nxi∈{0,1}x = \sum_{i=1}^n{x_i} \in \{0,1\} (gdzie suma się skończyła ZZ\mathbb{Z}). Jaka jest złożoność ustalenia, czyx=1x=1x = 1? Zauważ, że w trywialny sposób...
Jakie są jedne z najlepszych źródeł (książek i artykułów), które same w sobie motywują i uczą się złożoności komunikacji oraz w związku z jej relacją do teorii złożoności
Rozważ klasyczny problem # P-zupełny nr 3SAT, tj. Policz liczbę wycen, aby uzyskać 3CNF z nnnzmienne zadowalające. Interesuje mnie przybliżalność addytywna . Najwyraźniej istnieje prosty algorytm do osiągnięcia2)n - 12n−12^{n-1}- błąd, ale jeśli k <2)n -
Homomorfizm z wykresuG=(V,E)G=(V,E)G = (V, E)na wykresie jest odwzorowaniem od do taki sposób, że jeśli i są obok siebie w czym i sąsiadują z . Endomorfizm grafu jest homomorfizmem od do siebie; nie ma ustalonego punktu, jeśli nie ma takiego, że i nie jest trywialne, jeśli nie jest to...
Jaki jest najlepszy wynik dla liczby bramek w obwodzie pomnożącym dwie liczby całkowite n-bitowe? Oczywista metoda generuje bramki . Istnieją lepsze podejścia z i .θ(n2)θ(n2)\theta(n^2)θ(nlognloglogn)θ(nlognloglogn)\theta(n\log n \log\log n)θ(nlogn2log∗(n))θ(nlogn2log∗(n))\theta(n\log...
Powiedzmy, że mamy funkcję boolowską fa: { - 1 , 1}n→ { - 1 , 1 }f:{−1,1}n→{−1,1}f:\{-1,1\}^n\rightarrow \{-1,1\} i aplikujemy δδ\delta-losowe ograniczenie na faff. Ponadto powiedz, że drzewo decyzyjneT.TT to oblicza faff zmniejsza się O ( 1 )O(1)O(1)w wyniku losowego ograniczenia. Czy to implikuje...
Niech będzie wielomianem podanym przez obwód arytmetyczny o rozmiarze . Biorąc pod uwagę jako dane wejściowe, czy istnieje algorytm deterministyczny, aby sprawdzić, czy wszystkie nieredukowalne czynniki w są formami liniowymi? W pokrewnej uwadze, biorąc pod uwagę postać liniową , możemy sprawdzić...
Naprawmy kodowanie maszyn Turinga i uniwersalnej maszyny Turinga U, która na wejściu (T, x) wypisuje dowolne T na wejściu x (być może oba działają wiecznie). Zdefiniuj złożoność Kołmogorowa dla x, K (x), jako długość najkrótszego programu, p, tak aby U (p) = x. Czy istnieje takie N, że dla...
Interesują mnie wydajne algorytmy przecięcia DFA w szczególnych przypadkach. Mianowicie, gdy DFA przecinają się, zachowują określoną strukturę i / lub działają na ograniczonym alfabecie. Czy jest jakieś źródło, w którym mogę znaleźć algorytmy takich przypadków? Aby pytanie nie było zbyt szerokie,...
Szukam dowodu, że złożoności Kołmogorowa nie da się obliczyć, stosując redukcję z innego problemu nieobliczalnego. Powszechnym dowodem jest formalizacja paradoksu Berry'ego, a nie redukcja, ale powinien istnieć dowód poprzez redukcję z czegoś takiego jak problem zatrzymania lub problem...