Pytania otagowane jako conditional-results

Dodaj X jako hipotezę, gdzie X nie jest ani prawdziwe, ani fałszywe.

2
Czy można wzmocnić P = NP poza P = PH?
W złożoności opisowej Immerman ma Wniosek 7.23. Następujące warunki są równoważne: 1. P = NP. 2. Przekroczone, uporządkowane struktury, FO (LFP) = SO. Można to uznać za „wzmocnienie” P = NP do równoważnego wyrażenia w (przypuszczalnie) większych klasach złożoności. Zauważ, że SO przechwytuje wielomianową hierarchię czasu PH, a FO (LFP) …
4
Jakie są konsekwencje
Wiemy, że L⊆NL⊆PL⊆NL⊆P\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{P} i że L⊆NL⊆L2⊆L⊆NL⊆L2⊆\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{L}^2 \subseteq polyLpolyL\mathsf{polyL} , gdzie L2=DSPACE(log2n)L2=DSPACE(log2⁡n)\mathsf{L}^2 = \mathsf{DSPACE}(\log^2 n) . Wiadomo również, że polyL≠PpolyL≠P\mathsf{polyL} \neq \mathsf{P}ponieważ ten drugi ma całkowite problemy w przestrzeni logarytmicznej, wielokrotne redukcje jeden-jedynki, podczas gdy ten drugi nie (ze względu na twierdzenie o …
3
Czy implikuje ?
O ile rozumiem, program teorii geometrycznej złożoności próbuje oddzielić , udowadniając, że permament macierzy o złożonej wartości jest znacznie trudniejszy do obliczenia niż wyznacznik.VP≠VNPVP≠VNPVP \neq VNP Pytanie, które zadałem po przejrzeniu dokumentów GCT: Czy to natychmiast oznaczałoby , czy jest to tylko duży krok w kierunku tego celu?P≠NPP≠NPP \neq NP
3
Konsekwencje NC = P?
Zoo złożoności wskazuje we wpisie na EXP, że jeśli L = P, to PSPACE = EXP. Ponieważ NPSPACE = PSPACE autorstwa Savitcha, o ile mogę powiedzieć, podstawowy argument dopełniania rozszerza się, aby pokazać, że Wiemy również, że L NL NC \ subseteq P poprzez zmienną hierarchię ograniczoną zasobami Ruzzo.(NL=P)⇒(PSPACE=EXP).(NL=P)⇒(PSPACE=EXP).(\text{NL} = …
2
Konsekwencje
Jako amator TCS czytam popularny materiał wprowadzający na temat komputerów kwantowych. Oto kilka podstawowych elementów informacji, których nauczyłem się do tej pory: Komputery kwantowe nie są znane z rozwiązywania problemów NP-zupełnych w czasie wielomianowym. „Magia kwantowa nie wystarczy” (Bennett i in. 1997): jeśli odrzucisz strukturę problemu i po prostu weźmiesz …
2
Status światów Impagliazzo?
W 1995 r. Russell Impagliazzo zaproponował pięć światów złożoności: 1- Algorytmika: ze wszystkimi niesamowitymi konsekwencjami.P.= NP.P.=N.P.P=NP 2- Heuristica: problemy kompletne są trudne w najgorszym przypadku ( ), ale można je skutecznie rozwiązać w przeciętnym przypadku.N.P.N.P.NPP.≠ N.P.P.≠N.P.P \ne NP 3- Pessiland: Występują problemy z niepełną średniej wielkości przypadków , ale funkcje …
4
Twardość aproksymacji przy założeniu NP! = CoNP
Dwa typowe założenia potwierdzające twardość wyników aproksymacji to i Unique Games Conjecture. Czy jest jakaś twardość wyników aproksymacji przy założeniu, że ? Szukam problemu takiego, że „trudno jest zbliżyć do współczynnika chyba że ”.P≠NPP≠NPP \neq NPNP≠coNPNP≠coNPNP \neq coNPAAAAAAαα\alphaNP=coNPNP=coNPNP = coNP Wiadomym jest, że „pokazuje współczynnik NP twardość najkrótszym problemu wektora …
5
Dowód, że PPAD jest trudny?
Często cytowane jest filozoficzne uzasadnienie, by wierzyć, że P! = NP nawet bez dowodu. Inne klasy złożoności mają dowody na ich odrębność, ponieważ jeśli nie, miałyby „zaskakujące” konsekwencje (takie jak upadek hierarchii wielomianowej). Moje pytanie brzmi: jaka jest podstawa przekonania, że ​​klasa PPAD jest trudna do rozwiązania? Gdyby istniał algorytm …
3
Konsekwencje istnienia silnie wielomianowego algorytmu programowania liniowego?
Jednym ze świętych graali projektowania algorytmów jest znalezienie silnie wielomianowego algorytmu programowania liniowego, tj. Algorytmu, którego czas działania jest ograniczony wielomianem w liczbie zmiennych i ograniczeń i jest niezależny od wielkości reprezentacji parametrów (przy założeniu arytmetyka kosztów jednostkowych). Czy rozwiązanie tego pytania miałoby implikacje poza lepszymi algorytmami programowania liniowego? Na …
3
Problem decyzyjny, o którym nie wiadomo, że występuje w PH, ale będzie w P, jeśli P = NP
Edycja : Jak Ravi Boppana słusznie wskazał w swojej odpowiedzi, a Scott Aaronson dodał również inny przykład w swojej odpowiedzi , odpowiedź na to pytanie okazała się „tak” w sposób, którego w ogóle się nie spodziewałam. Najpierw pomyślałem, że nie odpowiedzieli na pytanie, które chciałem zadać, ale po pewnym zastanowieniu …
2
Powody, by wierzyć
To pytanie zostało przeniesione z Computer Science Stack Exchange, ponieważ można na nie odpowiedzieć na Theoretical Computer Science Stack Exchange. Migrował 6 lat temu . Wydaje się, że wiele osób uważa, że , po części dlatego, że wierzą, że faktoring nie jest możliwy do rozwiązania. (Shiva Kintali wymienił tutaj kilka …
2
Jakie są konsekwencje parzystości-L = P?
Parzystość-L jest zestawem języków rozpoznawanych przez niedeterministyczną maszynę Turinga, która może jedynie rozróżniać między liczbą parzystą lub nieparzystą liczbą ścieżek „akceptacji” (zamiast zerowej lub niezerowej liczby ścieżek akceptacji), i która jest dodatkowo ograniczone do pracy w przestrzeni logarytmicznej. Rozwiązanie liniowego układu równań powyżej ℤ 2 jest kompletnym problemem dla parzystości-L, …
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.