Pytania otagowane jako complexity-classes

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

1
Na rzadkich kompletach i P vs L.
Twierdzenie Mahaneya mówi nam, że jeśli istnieje rzadki zestaw przy wielomianowych redukcjach wielokrotności jeden, to . (Patrz „ Rzadkie kompletne zestawy dla NP: Rozwiązanie przypuszczenia Bermana i Hartmanisa ”)NPNPNPP=NPP=NPP = NP Czy znane są konsekwencje istnienia rzadkich kompletnych zestawów dla innych klas złożoności? W szczególności, jeśli w obszarze logarytmicznym występuje …
1
Domysł: Wszystkie języki FPT NP-complete mają stały parametr izomorficzny
Hipoteza Bermana – Hartmanisa: wszystkie języki NP-zupełne wyglądają podobnie, w tym sensie, że mogą być ze sobą powiązane przez wielomianowe izomorfizmy czasowe [1]. Interesuje mnie bardziej szczegółowa wersja „czasu wielomianowego”, to znaczy, jeśli zastosujemy sparametryzowane redukcje. Problem sparametryzowany to podzbiór , gdzie jest skończonym alfabetem, a to zbiór liczb nieujemnych. …
1
Czy równania różniczkowe można zaklasyfikować do własnych klas złożoności?
Problemy zostały sklasyfikowane jako całość dzięki złożoności obliczeniowej. Ale czy w równaniach różniczkowych można klasyfikować równania różniczkowe w zależności od ich struktury obliczeniowej? Na przykład, jeśli równanie niejednorodne pierwszego rzędu jest stosunkowo trudne do rozwiązania niż, powiedzmy, równanie jednorodne 100 rzędu, czy można je zaklasyfikować jako osobne klasy wypukłości, biorąc …
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
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} …
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 …
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 można zastosować opisową złożoną wersję twierdzenia Rice'a do oddzielenia AC0 i PSPACE?
W tym pytaniu wspomniano, że istnieją opisowe wersje złożoności twierdzenia Rice'a. Znalazłem dowód na następujące twierdzenie: Biorąc pod uwagę klasę złożoności C , nietrywialnych właściwości języków w C nie można obliczyć w C Wcześniej opublikowałem znaleziony dowód, ale ponieważ był on tak długi i ponieważ w komentarzach wskazano, że ten …
2
Czy znana jest jakaś klasa złożoności zawierająca internetowe odpowiedniki problemów związanych z optymalizacją?
Czy znana jest jakaś klasa złożoności zawierająca internetowe odpowiedniki problemów związanych z optymalizacją? Jeśli nie, to jak można zdefiniować taką klasę? Wiemy, że wiele problemów ma swoją wersję online: np. Wersja online problemu pakowania bin. Problemy online są trudniejsze, ponieważ mierzone są ich współczynnikami konkurencyjności. I nie znalazłem niczego podobnego …
1
Jakie są złożoności następujących podzbiorów SAT?
Załóżmy, żeP.≠ N.P.P≠NPP \neq NP Do tetracji użyj następującego zapisu (tj. ).jazaia{}^iajaa = aza⋅⋅⋅zaja razyia=aa⋅⋅⋅a⏟i times{}^ia = \underbrace{a^{a^{\cdot^{\cdot^{\cdot^{a}}}}}}_{i \mbox{ times}} | x | jest wielkością instancji x. Niech L będzie językiem,L |fa( i ) ≤ | x | &lt; g( i ):={x∈L | ∃i∈N, f(i)≤|x|&lt;g(i)}L|f(i)≤|x|&lt;g(i):={x∈L | ∃i∈N, f(i)≤|x|&lt;g(i)}L|_{f(i)\leq |x| < …
5
Klasy złożoności dla przypadków innych niż „najgorszy przypadek”
Czy mamy klasy złożoności w odniesieniu do, powiedzmy, złożoności średnich przypadków? Na przykład, czy istnieje (nazwana) klasa złożoności dla problemów, których podjęcie wymaga wielomianu? Kolejne pytanie dotyczy złożoności najlepszych przypadków , których przykłady przedstawiono poniżej: Czy istnieje klasa (naturalnych) problemów, których decyzja wymaga co najmniej wykładniczego czasu? Aby to wyjaśnić, …
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.