Pytania otagowane jako cc.complexity-theory

P a NP i inne obliczenia ograniczone do zasobów.

1
Pobieranie próbek zadowalających wzorów 3-SAT
Rozważ następujące zadanie obliczeniowe: Chcemy pobrać próbkę 3-SAT formuły zmiennych (wariant: zmiennych klauzule m ) w odniesieniu do równomiernego rozkładu prawdopodobieństwa, pod warunkiem spełnienia wzoru:nnnnnnmmm P1: Czy można to skutecznie osiągnąć za pomocą klasycznego komputera (z losowymi bitami)? P2: Czy można to skutecznie osiągnąć za pomocą komputera kwantowego? Interesują mnie …
3
Problemy z optymalizacją przy dobrej charakterystyce, ale bez algorytmu czasu wielomianowego
Rozważ problemy z optymalizacją w poniższym formularzu. Niech f(x)f(x)f(x) będzie funkcją obliczalną w czasie wielomianowym, która odwzorowuje ciąg xxx na liczbę wymierną. Problem optymalizacji jest następujący: jaka jest maksymalna wartość f(x)f(x)f(x) ponad nnn bitowych ciągów xxx ? gggmaxxf(x)=minyg(y)maxxf(x)=minyg(y)\max_x f(x) = \min_y g(y)xxxnnnyyymmmnnnmmm Wiele naturalnych i ważnych problemów związanych z optymalizacją …
6
Zaawansowane techniki określania dolnych granic złożoności
Niektórzy z was mogli śledzić to pytanie , które zostało zamknięte z powodu braku poziomu badań. Wyciągam więc część pytania, która jest na poziomie badawczym. Oprócz „prostszych” technik, takich jak redukcja do sortowania lub problem z WYŁĄCZENIEM, jakie techniki zostały zastosowane, aby udowodnić dolne granice złożoności problemu w czasie? W …
1
Chcę, aby prosty gadżet udowodnił, że cyklarny plan Hamiltonian NP-Complete (od cyklu Hamiltonian)
Wiadomo, że cykl hamiltonowski (w skrócie szynka) jest zakończony NP, a cykl szynki Planar jest zakończony NP. Dowód na cykl szynkowy nie pochodzi z cyklu szynkowego. Czy jest fajny gadżet, który, biorąc pod uwagę wykres G, zastąpi wszystkie skrzyżowania jakimś płaskim gadżetem, dzięki czemu masz płaski wykres G 'taki, że …
2
Naturalna redukcja CLIQUE do k-Color
Widoczna jest redukcja z CLIQUE na k-Color, ponieważ oba są NP-Complete. W rzeczywistości mogę go zbudować, tworząc redukcję z CLIQUE do 3-SAT z redukcją z 3-SAT do k-Color. Zastanawiam się, czy istnieje rozsądna bezpośrednia redukcja między tymi problemami. Powiedzmy, redukcję, którą mógłbym wyjaśnić przyjacielowi dość krótko, bez potrzeby opisywania języka …
1
Co wiadomo na temat złożoności znalezienia minimalnych obwodów dla SAT?
Co wiadomo o złożoności znalezienia minimalnych obwodów, które obliczają SAT do długości ? nnn Bardziej formalnie: jaka jest złożoność funkcji, która, biorąc pod uwagę jako wejście, generuje minimalny obwód taki, że dla dowolnej formuły z , ?1n1n1^{n}CCCφφ\varphi|φ|≤n|φ|≤n|\varphi| \leq nC(φ)=SAT(φ)C(φ)=SAT(φ)C(\varphi) = SAT(\varphi) (Szczególnie interesują mnie dolne granice). Naiwny deterministyczny algorytm (oblicz …
1
Algorytmy przestrzeni logów na wykresach z ograniczoną szerokością drzewa
Szerokość drzewa mierzy, jak blisko wykresu znajduje się drzewo. Trudno jest obliczyć szerokość drzewa. Najbardziej znany algorytm aproksymacyjny osiąga współczynnik .O ( log n----√)O(logn)O(\sqrt{{\log}n}) Twierdzenie Courcelle'a stwierdza, że dowolną właściwość grafów definiowalną w monadycznej logice drugiego rzędu (MSO2) można rozstrzygać w czasie liniowym na dowolnej klasie wykresów o ograniczonej szerokości …
1
Czy
W ankiecie „Małe głębokości obwodów kwantowych” D. Bery, F. Greena i S. Homera (s. 36 z ACM SIGACT News, czerwiec 2007 t. 38, nr 2) przeczytałem następujące zdanie: Klasyczna wersja (w której bramki i mają co najwyżej stały wentylator) jest wyraźnie słabsza niż .QAC0QAC0QAC^0ANDANDANDORORORAC0AC0AC^0 Brak odniesienia do tego roszczenia. Nazwę …
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.