Wielu wierzy, że . Jednak wiemy tylko, że B P P znajduje się na drugim poziomie hierarchii wielomianowej, tj. B P P ⊆ Σ P 2 ∩ Π P 2 . Etap kierunku pokazano B P P = P jest najpierw doprowadzić go do pierwszego poziomu hierarchii, to znaczy wielomian B P P ⊆ N P .BPP=P⊆NPBPP=P⊆NP\mathsf{BPP} =...
Czy są jakieś przykłady zabawek, które zapewniają „niezbędny” wgląd w trzy znane bariery dla problemu - relatywizacja, dowody naturalne i algebryzacja?P=NPP=NPP =
Powszechnie wiadomo, że każdy dowód rozwiązujący pytanie P vs NP musi pokonać relatywizację , dowody naturalne i bariery algebrizacyjne . Poniższy schemat dzieli „przestrzeń próbną” na różne regiony. Na przykład RNRNRN odpowiada zestawowi dowodów relatywizujących i naturalizujących. GCTGCTGCT...
Niedawno Ryan Willams udowodnił, że konstruktywność w naturalnym dowodzie jest nieunikniona, aby uzyskać separację klas złożoności: i . T C 0NEXPNEXP\mathsf{NEXP}TC0TC0\mathsf{TC}^{0} Konstruktywność w naturalnym dowodzie jest warunkiem, że wszystkie dowody kombinatoryczne w złożoności obwodu są...
Dokładne sformułowanie tytułu należy do Ananda Kulkarniego (który zaproponował utworzenie tej strony). To pytanie zostało zadane jako przykładowe, ale jestem niesamowicie ciekawy. Wiem bardzo mało o geometrii algebraicznej, a tak naprawdę posiadam jedynie pobieżne, licencjackie rozumienie przeszkód...
Dowody naturalne stanowią barierę dla udowodnienia niższych granic złożoności obwodu funkcji boolowskich. Nie bezpośrednio wynika, takiej bariery dla udowodnienia niższe granice na obwód złożoności. Czy jest jakiś postęp w identyfikowaniu takich barier? Czy istnieją inne bariery w ustawieniu...
Wszyscy wiemy, że pokazanie ma bariery. Wszyscy badaliśmy te bariery, ponieważ uważamy, że P ≠ N P.P≠NPP≠NPP\ne NPP≠NPP≠NPP\ne NP . Załóżmy jednak, że i są mądrzy ludzie, którzy wierzą, że taka możliwość istnieje . Jeśli tak rzeczywiście jest, to sam fakt, że nie widzieliśmy żadnych dobrych...
Nie pamiętam, że widziałem separację klas nieopartą na wynikach diagonalizacji i relatywizacji. Diagonalizacja może być nadal używana do oddzielania pozostałych znanych klas, ponieważ argumenty nierelatywizujące mogą być nadal stosowane w konkluzji o diagonalizacji lub w konstrukcji...
To kontynuacja mojego poprzedniego pytania: Najbardziej znana deterministyczna złożoność czasu dolna granica naturalnego problemu w NP Uważam za zdumiewające, że nie byliśmy w stanie udowodnić żadnego kwadratowego deterministycznego czasu w dolnej granicy jakiegokolwiek interesującego problemu...
Czy naturalne dowody , relatywizacja i algebriacja wpływają również na separację innych klas złożoności, takich jakL≠NL≠NP≠coNP≠PH≠PSPACEL≠NL≠NP≠coNP≠PH≠PSPACEL\neq NL\neq NP\neq coNP \neq PH\neq PSPACE itp? Na przykład bariera naturalnego dowodu powinna wpływać na każdy dowód NP≠CoNPNP≠CoNPNP\neq...