Pytania otagowane jako complexity-classes

Klasy złożoności obliczeniowej i ich relacje

2
Intuicja dla klasy UP
Klasa UP jest zdefiniowana jako taka: Klasa problemów decyzyjnych rozwiązanych przez maszynę NP, taką jak Jeśli odpowiedź brzmi „tak”, akceptuje dokładnie jedną ścieżkę obliczeniową. Jeśli odpowiedź brzmi „nie”, wszystkie ścieżki obliczeniowe odrzucają. Próbuję rozwinąć intuicję dla tej definicji. Czy można powiedzieć, że problemy UP są problemami z unikalnymi rozwiązaniami (np. …
1
Mechanizm dostępu do wyroczni Ruzzo-Simon-Tompa
W artykule na temat relatywizacji obliczeń przestrzeni logicznej Ladner i Lynch konstruują wyrocznię, do której . W literaturze można znaleźć więcej patologicznych przykładów. Czytałem kilka artykułów na temat relatywizowanych małych klas kosmicznych, a jednym z podstawowych narzędzi w tym obszarze jest mechanizm dostępu do wyroczni Ruzzo-Simon-Tompa (RST), który wymaga deterministycznej, …
3
Czy P zawiera niezrozumiałe języki? (Wiki społeczności TCS)
Odpowiedź: nieznana Ogromne podziękowania dla wszystkich, którzy pomogli dopracować to pytanie i związane z nim definicje. Definicje tej wiki stanowiły punkt wyjścia dla najnowszej wiki TCS „ Czy P zawiera języki, których istnienie jest niezależne od PA lub ZFC? (Wiki społeczności TCS) ”. Preferowana jest nowsza wiki, ponieważ jej definicje …
1
Jaka jest złożoność obliczania liczby rozwiązań problemu P-Space Complete? Co powiesz na klasy o wyższej złożoności?
Chyba nazywa się to # P-Space, ale znalazłem tylko jeden artykuł niejasno o tym wspominając. Co powiesz na liczącą się wersję problemów EXP-TIME-Complete, NEXP-Complete oraz EXP-SPACE-Complete? Czy są jakieś wcześniejsze prace, które można przytoczyć w odniesieniu do tego lub dowolnego rodzaju włączenia lub wyłączenia, takiego jak Toda's Torem?
4
Czy diagonalizacja oddaje istotę separacji klasowej?
Nie pamiętam, że widziałem separację klas nieopartą na wynikach diagonalizacji i relatywizacji. Diagonalizacja może być nadal używana do oddzielania pozostałych znanych klas, ponieważ argumenty nierelatywizujące mogą być nadal stosowane w konkluzji o diagonalizacji lub w konstrukcji diagonalizowanej maszyny Turinga. Oto kilka powiązanych pytań: Czy istnieją dowody separacji klas nieoparte na …
4
Klasa złożoności NEXP
Mam problem, który jest w NEXP NP i który może być rozwiązany przez przemienną TM przy użyciu czasu wykładniczego i tylko jednej alternacji (zaczynając od stanu egzystencjalnego).NPNP^{\text{NP}} Czy jest coś znanego na temat NEXP NP ? Czy jest równy NEXP lub innej klasie? Czy istnieją inne problemy niż ogólne (biorąc …
3
Jakie algorytmy można wyrazić za pomocą całkowitego języka funkcjonalnego z operatorami równoległych danych?
Wyobraź sobie funkcjonalny język programowania, którego jedynymi typami danych są skalary numeryczne i dowolne zagnieżdżenia tablic. W języku nie ma żadnych możliwości nieograniczonej iteracji, dlatego następujące elementy są niedozwolone: wyraźne pętle (i tak niewiele zużyć bez skutków ubocznych) rekurencja arbitralne funkcje pierwszej klasy (bez kombinatora y) Język ma jednak: funkcje …
3
Dwa warianty NP
Oto dwie odmiany definicji NP. (Prawie na pewno) definiują odrębne klasy złożoności, ale moje pytanie brzmi: czy istnieją naturalne przykłady problemów, które pasują do tych klas? (Mój próg, który jest tutaj naturalny, jest nieco niższy niż zwykle). Klasa 1 (nadklasa NP): problemy ze świadkami wielomianowymi, których weryfikacja wymaga czasu wielobiegunowego, …
2
Przykład czegoś innego dla ogólnych i losowych wyroczni?
Niech będzie ogólną wyrocznią w sensie kategorii Cohen / Baire. Niech będzie losową wyrocznią.GGGRRR Czy istnieją klasy złożoności A i B z lub na odwrót, AG=BGandAR≠BRAG=BGandAR≠BR\mathrm{A}^G=\mathrm{B}^G\quad\text{and}\quad\mathrm{A}^R\ne \mathrm{B}^RAG≠BGandAR=BR?AG≠BGandAR=BR?\mathrm{A}^G\ne\mathrm{B}^G\quad\text{and}\quad\mathrm{A}^R= \mathrm{B}^R\text{?} Pytanie zostało zainspirowane komentarzem Scotta Aaronsona .
2
Czy wyroki są stowarzyszone?
To pytanie może mieć oczywistą odpowiedź ... ale oto i tak pytanie. Intuicyjnie jest to następujące prawdopodobne stwierdzenie - „maszyna z podprogramem A, który z kolei ma podprogram B, jest tym samym, co maszyna z podprogramem A, który ma dostęp do podprogramu B”. Aby formalnie zdefiniować ten problem, użyję niekonwencjonalnej …
1
Jaka jest złożoność tej gry?
To jest uogólnienie mojego poprzedniego pytania . Niech będzie wielomianem czasie deterministyczny urządzenie, które może zadać pytania do jakiegoś oracle . Początkowo jest puste, ale można to zmienić po grze, która zostanie opisana poniżej. Niech będzie ciągiem znaków.MMMAAAAAAxxx Rozważ następującą grę Alice and Bob. Początkowo Alice i Bob mają odpowiednio …
1
Czy ta gra jest EXPSPACE?
Niech będzie wielomianem czasie deterministyczny urządzenie, które może zadać pytania do jakiegoś oracle A . Początkowo A jest puste, ale można to zmienić po grze, która zostanie opisana poniżej. Niech x będzie ciągiem znaków.M.MMZAAAZAAAxxx Rozważ następującą grę Alice and Bob. Początkowo Alice i Bob mają odpowiednio i m B dolarów. …
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.