Teoretyczne informatyka

Pytania i odpowiedzi dotyczące teoretycznych informatyków i badaczy w pokrewnych dziedzinach

1
Redukcja przestrzeni logów z obwodów Parity-L na obwody CNOT?
Pytanie. W swoim artykule Ulepszona symulacja obwodów stabilizatora , Aaronson i Gottesman twierdzą, że symulacja obwodu CNOT jest zakończona w ⊕L (przy zmniejszeniu przestrzeni logarytmicznej). Oczywiste jest, że jest on zawarty w ⊕L ; jak zachowuje się wynik twardości? Równoważnie: czy występuje ograniczenie przestrzeni logicznej z iterowanych produktów macierzy modulo …
1
Dokładny algorytm dla problemu znakowania krawędzi w DAG
Wdrażam część systemu, która wymaga pomocy. Dlatego kadruję go jako problem graficzny, aby uczynić go niezależnym od domeny. Problem: Otrzymujemy ukierunkowany wykres acykliczny . Bez utraty ogólności załóżmy, że G ma dokładnie jeden wierzchołek źródłowy s i dokładnie jeden wierzchołek tonący ; pozwolić P oznacza zbiór wszystkich skierowanych ścieżek z …
1
Idealne dopasowania na szachownicy?
Zastanów się nad problemem znalezienia maksymalnej liczby rycerzy, którzy mogą zostać postawieni na szachownicy bez atakowania się dwóch z nich. Odpowiedź brzmi 32: nie jest zbyt trudno znaleźć idealne dopasowanie (wykres wywołany ruchami rycerza jest dwustronny, i istnieje idealne dopasowanie dla planszy 4 × 4), co jest oczywiście minimalną osłoną …
4
Nieskończenie duże, ale lokalnie skończone problemy obliczeniowe
To pytanie jest inspirowane komentarzem Jukki Suomeli do innego pytania . Jakie są przykłady nieskończenie dużych, ale lokalnie skończonych problemów obliczeniowych (i algorytmów)? Innymi słowy, jakie są przykłady obliczeń, które zatrzymują się w skończonym czasie, w których każda Maszyna Turinga odczytuje i przetwarza tylko dane skończone, ale w sumie obliczenia …
3
Rozdzielenie wstępnie przetworzonego wielościanu i płaszczyzny
Mam poważne problemy ze zrozumieniem jednego kroku w pracy Dobkina i Kirkpatricka o rozdzieleniu wielościanów. Próbuję zrozumieć tę wersję: http://www.cs.princeton.edu/~dpd/Papers/SCG-09-invited/old%20papers/DPD+Kirk.pdf Twierdzi się, że gdy znamy najlepsze oddzielenie PiPiP_{i} i SSS , realizowanego przez ririr_i i sisis_i , można znaleźć oddzielenie Pi−1Pi−1P_{i-1} i SSS w O(1)O(1)O(1) schodów. Odbywa się to w …
1
kontra
Wiem, że PNP[logn]PNP[log⁡n]\mathsf{P}^{\mathsf{NP}[\log n]} (logarytmicznie wiele wywołań do NP oracle) jest równoważne PNP||PNP||\mathsf{P}^{\mathsf{NP}||}(wielomianowa liczba równoległych zapytań do NP oracle). Zastanawiałem się, czy wersja „funkcyjna” tych klas również jest równoważna, to znaczy czy Jeśli wiadomo, że to prawda, wskaźnik byłby naprawdę pomocny.FPNP[logn]=FPNP||FPNP[log⁡n]=FPNP|| \mathsf{FP}^{\mathsf{NP}[\log n]} = \mathsf{FP}^{\mathsf{NP}||}
2
Liczba triangulacji zbioru
Po tym, jak tego lata Emo Welzl przemawia na ten temat, wiem, że liczba triangulacji zbioru punktów na płaszczyźnie wynosi między około Ω ( 8,48 n ) a O ( 30 n ) . Przepraszam, jeśli jestem nieaktualny; aktualizacje mile widziane.nnnΩ ( 8,48n)Ω(8.48n)\Omega(8.48^n)O ( 30n)O(30n)O(30^n) Wspomniałem o tym na zajęciach …
3
Teoria złożoności, gdy wyrocznia jest częścią danych wejściowych
Najczęstszy sposób, w jaki wyrocznie występują w teorii złożoności, jest następujący: Stała wyrocznia jest udostępniana, powiedzmy, maszynie Turinga z pewnymi ograniczonymi zasobami, i jedna bada, w jaki sposób wyrocznia zwiększa moc obliczeniową maszyny. Istnieje jednak inny sposób, w jaki czasami zdarzają się wyrocznie: jako część danych wejściowych . Załóżmy na …
1
Ponowne użycie 5 niezależnych funkcji skrótu do sondowania liniowego
W tablicach skrótów, które rozwiązują kolizje za pomocą sondowania liniowego, w celu zapewnienia oczekiwanej wydajności , zarówno konieczne, jak i wystarczające jest, aby funkcja skrótu pochodziła z 5-niezależnej rodziny. (Wystarczalność: „Sondowanie liniowe ze stałą niezależnością”, Pagh i in. , Konieczność: „O k-niezależności wymaganej przez sondowanie liniowe i niezależność minutową”, Pătraşcu …
3
Jak mogę pokazać, że problem Gap-P jest poza #P
Istnieje wiele problemów w kombinatorycznej teorii reprezentacji i geometrii algebraicznej, dla których nie jest znana formuła dodatnia. Myślę o kilku przykładach, ale pozwólcie, że obliczę współczynniki Kroneckera jako mój przykład. Zwykle pojęcie „formuły dodatniej” nie jest precyzyjnie zdefiniowane w kombinatorykach, ale z grubsza oznacza „opis jako liczność zbioru rozsądnie wyraźnego”. …
1
Co wiadomo na temat interaktywnych proofów z wieloma dowodami z krótkimi wiadomościami?
Beigi, Shor i Watrous mają bardzo ładny artykuł na temat mocy kwantowych dowodów interaktywnych z krótkimi wiadomościami. Rozważają trzy warianty „krótkich wiadomości”, a konkretny, na którym mi zależy, to ich drugi wariant, w którym można wysłać dowolną liczbę wiadomości, ale całkowita długość wiadomości musi być logarytmiczna. W szczególności pokazują, że …
4
Teoretyczne badanie metod zejścia ze współrzędnymi
Przygotowuję materiały szkoleniowe na temat heurystyki do optymalizacji i szukam metod zejścia ze współrzędnymi. Ustawienie jest tu wielowymiarowa funkcja , które chcesz zoptymalizować. f ma właściwość ograniczoną do dowolnej pojedynczej zmiennej, którą łatwo zoptymalizować. Tak więc zejście współrzędnych odbywa się cyklicznie przez współrzędne, ustalając wszystko oprócz wybranego i minimalizując wzdłuż …
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.