Pytania otagowane jako logspace

2
Jakie są konsekwencje ?
Shiva Kintali właśnie ogłosił (zimne!) Co powoduje, że izomorfizm wykres dla ograniczonych wykresach treewidth szerokości IS -hard≥4≥4\geq 4⊕L⊕L\oplus L . Nieformalnie moje pytanie brzmi: „Jak trudne to jest?” Wiemy, że nierównomiernie , patrz odpowiedzi na to pytanie . Wiemy również, że jest mało prawdopodobne, aby , zobaczył odpowiedzi na to …
1
Złożoność wersji wyszukiwania 2-SAT przy założeniu
Jeśli , a następnie jest algorytm logspace który rozwiązuje wersja decyzja 2-SAT.L=NLL=NL\mathsf{L = NL} Czy wiadomo, że sugeruje, że istnieje algorytm przestrzeni logicznej, który pozwala uzyskać zadowalające przypisanie , jeśli dane wejściowe są zadowalające dla 2-SAT?L=NLL=NL\mathsf{L = NL} Jeśli nie, to co z algorytmami wykorzystującymi przestrzeń sublinearną (w liczbie klauzul)?
1
Czy
Co się stanie, jeśli zdefiniujemy P P A D wPPAD{\bf PPAD} taki sposób, że zamiast polytime-maszyny Turinga / obwodu polisize, maszyny logistycznej Turinga lub obwodu A C 0AC0{\bf AC^0} koduje problem? Ostatnio dając szybsze algorytmy Okręgowego spełnialności dla małych obwodów okazało się być ważne, więc zastanawiam się, co się dzieje …
1
Redukcja przestrzeni logów z obwodów Parity-L na obwody CNOT?
Pytanie. W swoim artykule Ulepszona symulacja obwodów stabilizatora , Aaronson i Gottesman twierdzą, że symulacja obwodu CNOT jest zakończona w ⊕L (przy zmniejszeniu przestrzeni logarytmicznej). Oczywiste jest, że jest on zawarty w ⊕L ; jak zachowuje się wynik twardości? Równoważnie: czy występuje ograniczenie przestrzeni logicznej z iterowanych produktów macierzy modulo …
1
Jakie są przeszkody w przedłużeniu
Dowód omer Reingold, że daje algorytm USTCON (W U ndirected wykres ze szczególnym wierzchołki s i t są one Con podłączeń z sieciami?) Za pomocą tylko logspace. Podstawową ideą jest zbudowanie wykresu ekspandera z oryginalnego wykresu, a następnie przejście do wykresu ekspandera. Wykres ekspandera jest tworzony przez wielokrotne kwadratowe obliczenie …
1
Duże klasy zawierające LOGSPACE, dla których ścisłe włączenia nie są znane
Strona wikipedii na PSPACE wspomina, że ​​włączenie nie jest znane jako ścisłe (niestety bez odnośników).NL⊂PHNL⊂PHNL\subset PH P1: Co z i - czy są one znane jako ścisłe?L⊂PHL⊂PHL\subset PHL⊂P#PL⊂P#PL\subset P^{\#P} P2: Jeśli nie, czy istnieje ustalona klasa która zawiera i dla której nie wiadomo, czy włączenie jest ścisłe?CCCP#PP#PP^{\#P}L⊂CL⊂CL\subset C P3: Czy …
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 …
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.