Pytania otagowane jako cc.complexity-theory

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

28
Problemy między P a NPC
Rozkładanie na czynniki i izomorfizm wykresów są problemami w NP, o których nie wiadomo, że są w P ani w NP-kompletne. Jakie są inne (wystarczająco różne) naturalne problemy, które dzielą tę właściwość? Sztuczne przykłady pochodzące bezpośrednio z dowodu twierdzenia Ladnera się nie liczą. Czy którykolwiek z tych przykładów może być …
14
Jakie podstawy matematyczne są potrzebne do teorii złożoności?
Obecnie jestem studentem, który w tym roku musi ukończyć studia. Po ukończeniu studiów rozważam pracę w kierunku magistra / doktora TCS. Zacząłem się zastanawiać, jakie dziedziny matematyki są uważane za pomocne w TCS, zwłaszcza (klasyczna) teoria złożoności. Jakie dziedziny uważasz za niezbędne dla kogoś, kto chce studiować teorię złożoności? Czy …
7
Jakie interesujące twierdzenia w TCS opierają się na Axiom of Choice? (Lub alternatywnie, aksjomat determinacji?)
Matematycy czasem martwią się o aksjomat wyboru (AC) i aksjomat determinacji (AD). Aksjomat wyboru : Biorąc pod uwagę dowolny zbiór z niepustych zestawach jest funkcja , które, biorąc pod uwagę zestaw w , zwraca element z .CC{\cal C}fffSSSCC{\cal C}SSS Aksjomat Determinacji : Niech będzie zbiorem nieskończenie długich ciągów bitów. Alice …
7
Czy problemy związane z są z natury mniej podatne na rozwiązanie niż problemy z ?
Obecnie rozwiązanie NPNPNP pełnego NP lub PSPACEPSPACEPSPACE jest niewykonalne w ogólnym przypadku dużych nakładów. Jednak oba można rozwiązać w czasie wykładniczym i przestrzeni wielomianowej. Skoro nie jesteśmy w stanie zbudować niedeterministycznych lub „szczęśliwych” komputerów, czy ma to dla nas jakąkolwiek różnicę, jeśli problemem jest NPNPNP lub PSPACEPSPACEPSPACE -kompletny?
1
Więcej na temat PH w PP?
Ostatnie pytanie za pytaniem, czy Huck Bennett PH klasa została zawarta w PP klasy, otrzymał nieco sprzecznych odpowiedzi (wszystko prawda, wydaje się). Z jednej strony podano przeciwnie kilka wyników wyroczni, z drugiej Scott zasugerował, że odpowiedź jest prawdopodobnie pozytywna, ponieważ twierdzenie Tody pokazuje, że PH jest w BP.PP, wariancie probabilistycznym …
8
Jaka klasa złożoności jest najbardziej związana z tym, co ludzki umysł może szybko osiągnąć?
Zastanawiam się nad tym pytaniem. Kiedy ludzie opisują problem P vs. NP, często porównują NP klasy do kreatywności. Zauważają, że skomponowanie symfonii jakości Mozarta (analogicznej do zadania NP) wydaje się znacznie trudniejsze niż sprawdzenie, czy już skomponowana symfonia ma jakość Mozarta (analogiczną do zadania P). Ale czy NP to naprawdę …
4
Dlaczego 2SAT w P?
Natknąłem się na algorytm wielomianowy, który rozwiązuje 2SAT. Uważam za zaskakujące, że 2SAT znajduje się w P, gdzie wszystkie (lub wiele innych) instancji SAT są NP-Complete. Co wyróżnia ten problem? Co sprawia, że ​​jest to takie proste (NL-Complete - nawet łatwiejsze niż P)?
3
Zaskakujące algorytmy liczenia problemów
Istnieją pewne problemy z liczeniem, które polegają na zliczaniu wykładniczo wielu rzeczy (w stosunku do wielkości danych wejściowych), a jednak mają zaskakujące algorytmy deterministyczne o czasie wielomianowym. Przykłady obejmują: Zliczanie idealnych dopasowań na wykresie planarnym ( algorytm FKT ), który jest podstawą działania algorytmów holograficznych . Zliczanie drzew rozciągających się …
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) …
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.