Pytania otagowane jako cc.complexity-theory

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

1
Kwadratowy związek między przestrzenią niedeterministyczną a deterministyczną?
Twierdzenie Savitcha pokazuje, że NSPACE(f(n))⊆DSPACE(f(n)2)NSPACE(f(n))⊆DSPACE(f(n)2)\mathrm{NSPACE}(f(n)) \subseteq \mathrm{DSPACE}(f(n)^2) dla wszystkich wystarczająco dużych funkcji fff , i udowodnienie, że jest ciasno, było otwartym problemem od dziesięcioleci . Załóżmy, że podchodzimy do problemu z drugiego końca. Dla uproszczenia załóżmy logiczny alfabet. Ilość miejsca wykorzystywanego przez TM do decydowania o języku obliczeniowym jest często …
3
Kategoria „maszyn Turinga”?
Zastrzeżenie: Wiem bardzo mało o teorii złożoności. Przepraszam, ale tak naprawdę nie ma sposobu, aby zadać to pytanie bez (strasznie) zwięzłego: Jakie powinny być morfizmy w „kategorii” maszyn Turinga? Jest to oczywiście subiektywne i zależy od interpretacji teorii, więc odpowiedź na to pytanie powinna idealnie dać pewne dowody i uzasadnienie …
3
Rozdzielanie klas czasowych
Mój student ostatnio zadał następujące pytanie: DTIME(f(n))⊊DTIME(g(n)).DTIME(f(n))⊊DTIME(g(n)).DTIME(f(n)) \subsetneq DTIME(g(n)).h(n)h(n)h(n)DTIME(f(n))⊊DTIME(h(n))⊊DTIME(g(n))?DTIME(f(n))⊊DTIME(h(n))⊊DTIME(g(n))?DTIME(f(n)) \subsetneq DTIME(h(n)) \subsetneq DTIME(g(n))? Prawdopodobnie można to udowodnić, konstruując jeśli są konstruowalne w czasie. Ale ogólnie uważam, że powinno to być fałszem podobne do .h(n)h(n)h(n)f,gf,gf,gDSPACE(o(log(log(n))))=DSPACE(1)DSPACE(o(log⁡(log⁡(n))))=DSPACE(1)DSPACE(o(\log(\log(n)))) = DSPACE(1)
2
O statusie zdolności uczenia się w
Próbuję zrozumieć złożoność funkcji wyrażanych przez bramki progowe, co doprowadziło mnie do . W szczególności interesuje mnie to, co obecnie wiadomo na temat uczenia się w T C 0 , ponieważ nie jestem ekspertem w tej dziedzinie.TC0TC0\mathsf{TC}^0TC0TC0\mathsf{TC}^0 Do tej pory odkryłem: Wszystkie można wyciągnąć w quasipolynomial czasie w jednorodnym rozkładzie …
3
Separacje klas złożoności bez twierdzeń hierarchicznych
Twierdzenia o hierarchii są podstawowymi narzędziami. Wiele z nich zebrano we wcześniejszym pytaniu (patrz Jakie hierarchie i / lub twierdzenia dotyczące hierarchii znasz? ). Niektóre separacje klas złożoności wynikają bezpośrednio z twierdzeń hierarchicznych. Przykłady takich dobrze znanych separacji: L ≠ PS.P.A C.miL≠PSPACEL\neq PSPACE , , , .N P ≠ N …
4
Problemy z grafem, które są NP-Complete na grafach ukierunkowanych, ale wielomianowe na grafach niekierowanych
Szukam problemów, które są znane jako NPC dla grafów kierowanych, ale mają algorytm wielomianowy dla grafów bezkierunkowych. Widziałem pytanie dotyczące odwrotnych problemów, które są łatwiejsze niż ich „niekierowany” wariant , ale szukam twardości po stronie ukierunkowanej. Na przykład, zestaw krawędzi sprzężenia zwrotnego jest znany jako NPC na ukierunkowanych, ale wielomianowych …
2
Jak mały może być NFA w porównaniu z minimalnym jednoznacznym automatem skończonym (UFA) tego samego języka regularnego?
Jednoznaczne automaty skończone (UFA) są specjalnym typem niedeterministycznych automatów skończonych (NFA). NFA jest nazywany jednoznacznym, jeśli każde słowo ma co najwyżej jedną ścieżkę akceptującą.w ∈ Σ∗w∈Σ∗w\in \Sigma^* Oznacza to, .D F.A ⊂ UfaA ⊂ NfaZArefaZA⊂UfaZA⊂N.faZADFA\subset UFA\subset NFA Znane powiązane wyniki automatów: Minimalizacja NFA jest kompletna z PSPACE. Minimalizacja NFA w …
1
Podejście Gowersa do „dyskretnej determinacji Borela”
Gowers przedstawił ostatnio problem, który nazywa „dyskretną determinacją Borela”, którego rozwiązanie dotyczy dolnych granic obwodu dowodzenia. Czy możesz podać podsumowanie podejścia, które jest dostosowane do grupy teoretyków złożoności? Co potrzeba, aby to podejście wykazało cokolwiek , w tym ponowne udowodnienie znanych dolnych granic?
2
Liniowe równanie diofantyny w liczbach całkowitych nieujemnych
Jest tylko bardzo mało informacji na temat kompletnego NP rozwiązania problemu liniowego równania diofantyny w liczbach całkowitych nieujemnych. To znaczy, czy jest to rozwiązanie w nieujemne x1,x2,...,xnx1,x2,...,xnx_1,x_2, ... , x_n do równania , gdzie wszystkie stałe są dodatnie? Jedyną godną uwagi wzmianką o tym problemie, który znam, jest Teoria programowania …
1
Naturalni kandydaci do hierarchii wewnątrz NPI
Załóżmy, że . N P ja to klasa problemów w N P , które nie są ani w P ani w N P -hard. Listę problemów, które można przypuszczać, że są N P I tutaj .P≠NPP≠NP\mathsf{P} \neq \mathsf{NP}NPINPI\mathsf{NPI}NPNP\mathsf{NP}PP\mathsf{P}NPNP\mathsf{NP}NPINPI\mathsf{NPI} Twierdzenie Ladnera mówi nam, że jeśli to istnieje nieskończona hierarchia problemów N …
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.