Pytania otagowane jako cc.complexity-theory

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

1
Naturalny problem w
Klasa złożoności jest zdefiniowana następująco (z Wikipedii ):SP2S.2)P.\textrm{S}_2^\textrm{P} Język znajduje się w S P 2, jeśli istnieje predykat P wielomianowy taki, żeLL.LSP2S.2)P.S_2^PPP.P Jeśli , to istnieje y takie, że dla wszystkich z , P ( x , y , z ) = 1x ∈ L.x∈L.x \in LyyyzzzP.( x , y, …
1
Dowody w
W przemówieniu Razborowa opublikowano dziwne oświadczenie. Jeśli FACTORING jest trudny, to małe twierdzenie Fermata nie jest możliwe do udowodnienia w S12S21S_{2}^{1} . Co to jest S12S21S_{2}^{1} i dlaczego aktualnych dowodów nie ma w S12S21S_{2}^{1} ?
1
Czy pseudolosowość deterministyczna jest prawdopodobnie silniejsza niż przypadkowość równolegle?
Niech klasa BPNC (kombinacja i ) będzie algorytmami równoległymi głębokości dziennika z ograniczonym prawdopodobieństwem błędu i dostępem do losowego źródła (nie jestem pewien, czy to ma inną nazwę). Podobnie zdefiniuj klasę DBPNC, z tym wyjątkiem, że wszystkie procesy mają losowy dostęp do losowego strumienia bitów ustalonego przy uruchomieniu algorytmu.N CBPPBPP\mathsf{BPP}NCNC\mathsf{NC} …
1
Bilansowanie formuł boolowskich w
Szukam referencji na temat złożoności problemu równoważenia formuł logicznych . W szczególności, Czy było wiadomo, że formuły logiczne można wyważyć w AC0AC0\mathsf{AC^0} ? Czy istnieje prosty dowód na to, że równoważenie boolowskiej formuły jest w AC0AC0\mathsf{AC^0} ? Przez „proste” mam na myśli dowód prostsze niż ten wspominam poniżej, w szczególności …
1
Dlaczego dolne granice dla obwodów boolowskich nie implikują niższych granic obwodów arytmetycznych
Moje pytanie brzmi: dlaczego dolne granice dla głębokości 3 Obwody logiczne z bramkami „i” i „xor” dla wyznacznika nie oznaczają takich samych dolnych granic dla obwodów arytmetycznych w ?ZZ\mathbb{Z} Co jest nie tak z następującym argumentem: Niech będzie wyznacznikiem obliczającym obwód arytmetyczny, a następnie biorąc wszystkie zmienne mod 2 otrzymamy …
3
Jaka jest najszybciej znana symulacja BPP z wykorzystaniem algorytmów Las Vegas?
BPPBPP\mathsf{BPP} iZ P PZPP\mathsf{ZPP} to dwie podstawowe probabilistyczne klasy złożoności. B P PBPP\mathsf{BPP} jest klasą języków ustaloną przez probabilistyczne algorytmy Turinga w czasie wielomianowym, w których prawdopodobieństwo zwrotu nieprawidłowej odpowiedzi przez algorytm jest ograniczone, tzn. Prawdopodobieństwo błędu wynosi maksymalnie13)13\frac{1}{3} (zarówno dla wystąpień TAK, jak i NIE). Z drugiej strony, algorytmy …
1
Błędy jednostronne w probablistycznych systemach dowodowych
W większości probabilistycznych systemów dowodowych (na przykład twierdzenie PCP) prawdopodobieństwa błędów są zwykle definiowane po stronie fałszywie dodatnich, tj. Typowa definicja może wyglądać tak: jeśli to weryfikator zawsze przyjmuje, ale w w innym przypadku prawdopodobieństwo odrzucenia wynosi co najmniej 1/2.x∈Lx∈Lx \in L Czy istnieje problem z dopuszczeniem wystąpienia błędu po …
2
O Inverse 3-SAT
Kontekst : Kavvadias i Sideri wykazali, że odwrotny problem 3-SAT jest coNP zakończony: Biorąc pod uwagę ϕϕ\phi zestaw modeli nnn zmiennych, czy istnieje wzór 3-CNF taki, że ϕϕ\phi jest jego dokładnym zestawem modeli? Powstaje formuła bezpośredniego kandydata, która jest połączeniem wszystkich 3-klauzul spełnionych przez wszystkie modele w ϕϕ\phi . Ponieważ …
1
Czy
W literaturze nie znalazłem stwierdzenia dotyczącego i ; wskazówki będą mile widziane.N P R PMAMA\mathsf{MA}NPRPNPRP\mathsf{NP}^\mathsf{RP} Wierzę, że są równi: N P R PMA⊆NPRPMA⊆NPRP\mathsf{MA} \subseteq \mathsf{NP}^\mathsf{RP} : Maszyna zgaduje ciąg Merlina, a wyrocznia weryfikuje ciąg tak, jak Arthur.NPNP\mathsf{NP}RPRP\mathsf{RP} NPRP⊆MANPRP⊆MA\mathsf{NP}^\mathsf{RP} \subseteq \mathsf{MA} : Merlin zgaduje obliczenia akceptujące maszyny , w tym wszystkie …
4
Wyniki Oracle dla P vs BPP
Niech będzie dowolnym EXP kompletnym problemem. Następnie .P A = N P AZAAAP.ZA= NP.ZAPA=NPAP^A = NP^A Niech będzie jakiś wyrocznią, która bierze pod rachunkach zapytań (a TM w P) uczynią, a my możemy dostać .M P B ≠ N P BbBBM.MMP.b≠ N.P.bPB≠NPBP^B \neq NP^B Pytanie: Czy mamy podobne wyniki wyroczni …
2
Decydujący homomorfizm grafowy
Graf decydujący Homomorfizm jest ogólnie NP-Complete. Czy istnieją wyniki, które badają ten problem, gdy leżące u podstaw wykresy mają strukturę algebraiczną (takie jak decydowanie o homomorfizmach z wykresów Coseleya lub Cayleya do innych wykresów o określonej strukturze również)? Oprócz wyników złożoności interesują mnie również pomocne techniki algebraiczne i / lub …
3
Jakim automatem jest Google Turing Doodle?
Z okazji urodzin Alana Turinga Google opublikował doodle przedstawiające maszynę. Jaką maszyną jest doodle? Czy może wyrażać język Turing Complete? Istnieją oczywiste różnice w stosunku do klasycznej maszyny Turinga: skończona taśma, ograniczenia w sposobie łączenia stanu, ... Doodle jest nadal dostępne tutaj (Wyświetlacz w prawym górnym rogu pokazuje oczekiwane wyjście.) …
1
Jednolity sposób kwantyfikacji „rozgałęzień” w obliczeniach niedeterministycznych, probabilistycznych i kwantowych?
Obliczenia niedeterministycznej maszyny Turinga (NTM) są dobrze znane jako drzewa konfiguracji, zakorzenione w konfiguracji początkowej. Każde przejście w programie jest reprezentowane przez łącze ojciec-dziecko w tym drzewie. Podobne drzewa można również skonstruować do wizualizacji obliczeń maszyn probabilistycznych i kwantowych. (Należy zauważyć, że dla niektórych celów lepiej jest nie wyświetlać powiązanego …
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.