Pytania oznaczone «cc.complexity-theory»

14
Jaka jest złożoność Median-SAT?

Niech będzie formułą CNF z n zmiennymi i klauzulami m . Niech t ∈ { 0 , 1 } n reprezentuje przypisanie zmiennej, a f φ ( t ) ∈ { 0 , … , m } zliczają liczbę klauzul spełnionych przez przypisanie zmiennej do φ . Następnie zdefiniuj Median-SAT jako problem obliczania mediany wartości f φ ( t ) dla...

14
Klasa złożoności odpowiadająca sortowaniu

Dwie części TCS to algorytmy i złożoność. Upraszczając powiem, że algorytmy to badanie górnych granic, pokazujące, że możesz coś zrobić (przy danych ograniczonych zasobach), a złożoność polega na pokazaniu, że nie możesz tego zrobić bez minimalnych zasobów. Tak często problem algorytmiczny pojawia...

14
kontra

Wiem, że PNP[logn]PNP[log⁡n]\mathsf{P}^{\mathsf{NP}[\log n]} (logarytmicznie wiele wywołań do NP oracle) jest równoważne PNP||PNP||\mathsf{P}^{\mathsf{NP}||}(wielomianowa liczba równoległych zapytań do NP oracle). Zastanawiałem się, czy wersja „funkcyjna” tych klas również jest równoważna, to...

14
Na złożoność minimalizacji przepustowości

Problem przepustowości wykresu jest zdefiniowany następująco. Biorąc pod uwagę wykres G=(V,E)G=(V,E)G=(V,E) , A układ fff z jest mapowanie jeden do jednego z wierzchołków na całkowite . Pasma określa się jakoG { 1 , … , | V | } fGGGGGG{1,…,|V|}{1,…,|V|}\{1, \ldots,...