Pytania oznaczone «cc.complexity-theory»

25
Złożoność „jest wykresem produkt”

To pytanie powstaje z czystej ciekawości (pojawiło się podczas myślenia o odtasowaniu łańcucha , ale nie jestem pewien, czy jest rzeczywiście powiązane), więc mam nadzieję, że jest odpowiednie. Istnieje wiele produktów graficznych i interesuje mnie którykolwiek z nich. Jaka jest złożoność...

25
Dowody, bariery i P vs NP

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...