Pytania otagowane jako cc.complexity-theory

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

2
Złożoność częściowych gier informacyjnych o skończonym stanie
Biorąc pod uwagę deterministyczną grę z sumą zerową z częściową informacją i tylko skończoną liczbą stanów, których możliwymi rezultatami są odpowiednio [przegrana, remis, wygrana] o wartościach odpowiednio [-1,0, + 1], jaka jest złożoność przybliżenia wartości takich gra w dodatku ?ϵϵ\epsilon W szczególności nie mogę wymyślić żadnego algorytmu do tego. Pozostała …
1
Jak trudna jest binarna łamigłówka Sudoku?
Sudoku jest dobrze znaną łamigłówką, która jest kompletna NP. Sudoku Binarne to wariant, który dopuszcza tylko cyfry i 1 . Zasady są następujące.000111 Każdy wiersz i każda kolumna musi zawierać równą liczbę zer i jedynek. Każdy wiersz i każda kolumna jest unikalny. Żaden wiersz ani kolumna nie zawiera kolejnych potrójnych …
1
Twierdzenie Schaefera i CSP o nieograniczonej szerokości
Twierdzenie dychotomii Schaefera pokazuje, że każdy problem CSP powyżej można rozwiązać w czasie wielomianowym lub jest on NP-kompletny. Dotyczy to tylko problemów CSP o ograniczonej szerokości, z wyłączeniem na przykład SAT i Horn-SAT. Ogólne problemy CSP o nieograniczonej szerokości mogą być bardzo trudne (nawet nieobliczalne), więc ograniczmy się do problemów, …
1
Optymalne solwery NP
Napraw problem wyszukiwania NP-complete, np. Formularz wyszukiwania SAT. Wyszukiwanie Levin zapewnia algorytm do rozwiązywania który jest w pewnym sensie optymalny. Konkretnie, algorytm jest „Wykonanie wszystkich możliwych programów w zazębianie na wejściowego , gdy niektórzy powraca odpowiedzieć testy czy jest to poprawna”. Jest optymalna w tym sensie, że biorąc pod uwagę …
1
Negatywne wyniki w podejściu identycznych cząstek do problemu Isomorphism Graph (GI)
Podjęto próby zaatakowania problemu izomorfizmu grafów za pomocą kwantowego losowego chodzenia twardych rdzeni (symetryczne, ale bez podwójnego zajęcia). Symetryczna moc matrycy przylegania, która wydawała się obiecująca, wykazano jako niekompletne ogólnych wykresów na tym papierze Amir Rahnamai Barghi i Ilia Ponomarenko. Inne podobne podejście zostało również obalone w tym artykule przez …
1
Czy algorytmy kwantowe z przyspieszeniem wykładniczym można ponownie odczytać za pomocą programów zakresu?
Wiadomo, że dolna granica ogólnego przeciwnika charakteryzuje złożoność kwantowych zapytań z powodu przełomowej pracy Reichardta i in. Ta sama linia pracy ustanawia również połączenia ze strukturą programu zakresu do projektowania algorytmów kwantowych. Wiele interesujących algorytmów kwantowych, w tym z przyspieszeniem wykładniczym, takich jak algorytm Simona i algorytm Shora do wyszukiwania …
2
Skuteczne uniwersalne narzędzie do rozwiązywania problemów?
Zdefiniuj „problem” jako algorytm akceptujący liczbę naturalną i zwracający 0 lub 1, która zwraca na co najmniej jednym . Każde takie nazywane jest „rozwiązaniem”AAA111n∈Nn∈Nn \in \mathbb{N}nnnAAA Zdefiniuj „uniwersalne narzędzie do rozwiązywania problemów” jako algorytm przyjmujący problem i zwracający jedno z jego rozwiązań. Na przykład może działać, zapętlając wszystkie liczby naturalne …
2
Złożoność przestrzeni w celu obliczenia optymalnego wyrównania łańcucha dla odległości edycji Levenshteina
Jeśli otrzymamy dwa ciągi o rozmiarze n1n1n_1 i , standardowe obliczanie odległości edycji Levenshteina odbywa się za pomocą algorytmu dynamicznego o złożoności czasowej i złożoności przestrzennej . (Niektóre ulepszenia można wprowadzić w zależności od odległości edycji , ale nie zakładamy, że jest szczególnie mały.) Jeśli interesuje Cię tylko wartość odległości …
3
AM / MA i NP analogicznie do P i BPP
Arora i Barak pokazują, że można wyrazić jako B P ⋅ N P, tj. Zestaw języków, w których losowe obniżki do 3SAT. M jest także naturalnym randomizowane uogólnienie N P w które zastąpi deterministyczny weryfikatora przez randomizowanym jeden.AMAM\mathsf{AM}BP⋅NPBP⋅NP\mathsf{BP}\cdot \mathsf{NP}MAMA\mathsf{MA}NPNP\mathsf{NP} Czy istnieje sens, w którym jedno z nich jest ściślej dopasowane …
2
Czy automaty wielopłytkowe mogą decydować o wszystkich deterministycznych językach kontekstowych?
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 symbol pod głową ma kamyk, a następnie może umieścić kamyk …
2
Ograniczenie pytań progowych do pytań skończoności
Zwykle łatwiej jest uzasadnić rachunek różniczkowy, w którym ograniczeniem jest skończoność obliczeń, a nie próg taki jak „obliczalny w wielomianowym czasie”. Na przykład w teorii języków formalnych, zamiast używać aby scharakteryzować aperiodic monoïd, łatwiej jest używać profinite wyrazów, aby .x ω + 1 = x ω∃ n . xn + …
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.