Pytania oznaczone «cc.complexity-theory»

27
Decydowanie, czy dany obwód

Jaka jest złożoność decyzji, czy obwód z n bitami wejściowymi i n bitami wyjściowymi oblicza permutację { 0 , 1 } n ? innymi słowy, czy każdy ciąg bitów w { 0 , 1 } n jest wyjściem obwodu dla niektórych danych wejściowych? Wygląda na problem, który został zbadany, ale nie mogę znaleźć żadnych...

27
Czy istnieje kandydat na naturalny problem w ?

Chcę wiedzieć, czy niejednorodność pomaga w praktyce funkcji obliczeniowych. Łatwo jest pokazać, że istnieją funkcje w , weź dowolną funkcję nieobliczalną i rozważ język { }, który wyraźnie ma proste niejednorodne obwody , ale w ogóle nie da się go obliczyć jednolicie, ale to nie są funkcje,...

26
Zwięzłe problemy w

Badanie KRÓTKI reprezentacją wykresów został zainicjowany przez Galperin i Wigderson w artykule z 1983 r, gdzie wykazać, że przez wiele problemów, takich jak proste znalezienie trójkąta na wykresie odpowiadający zwięzły wersji w -Complete. Papadimitriou i Yanakkakis ponadto ta linia badania i...

26
Problemy naturalne w

Czy występują jakieś naturalne problemy w , które nie są (wiadomo, że są / sądzi się, że są) w U P ∩ c o U P ?N.P.∩ c o NP.NP∩coNPNP \cap coNPUP.∩ c o UP.UP∩coUPUP \cap coUP Oczywiście wielki każdy wie o w jest wersja decyzja faktoringu (czy n mają współczynnik wielkości co najwyżej k), ale to...

26
Złożoność zasilania macierzy

Niech będzie kwadratową macierzą liczb całkowitych, a niech n będzie liczbą całkowitą dodatnią. Interesuje mnie złożoność następującego problemu decyzyjnego:MMMnnn Czy prawy górny wpis dodatni?MnMnM^n Zauważ, że oczywiste podejście iterowanego kwadratu (lub innego jawnego obliczenia) wymaga od...

26
Problemy pośrednie między L i NL

Jest dobrze wiadomo, że skierowane st-łączność jest -Complete. Przełom wynik Reingold wykazała, że nieukierunkowane st-łączność jest w L . Płaskie skierowane st-łączności jest znany w U L ∩ C O U L . Cho Huynh zdefiniowano sparametryzowanego problemu plecakowego i wykazywał hierarchię problemów...

26
Jakie są konsekwencje ?

Shiva Kintali właśnie ogłosił (zimne!) Co powoduje, że izomorfizm wykres dla ograniczonych wykresach treewidth szerokości IS -hard≥4≥4\geq 4⊕L⊕L\oplus L . Nieformalnie moje pytanie brzmi: „Jak trudne to jest?” Wiemy, że nierównomiernie , patrz odpowiedzi na to pytanie . Wiemy również, że jest mało...

26
Obliczanie wszelkich informacji o Max-3SAT

O wzorze 3CNF pozwolić jest w maksymalna liczba zadowoleni klauzul jakimkolwiek wyznaczeniem . Wiadomo, że wartość Max-3SAT jest trudna do przybliżenia (z zastrzeżeniem P ≠ NP), tj. Nie ma algorytmu czasu policyjnego, którego dane wejściowe to formuła 3CNF , a których wynikiem jest liczba taka, że...