Pytania otagowane jako complexity-classes

Często cytowane jest filozoficzne uzasadnienie, by wierzyć, że P! = NP nawet bez dowodu. Inne klasy złożoności mają dowody na ich odrębność, ponieważ jeśli nie, miałyby „zaskakujące” konsekwencje (takie jak upadek hierarchii wielomianowej). Moje pytanie brzmi: jaka jest podstawa przekonania, że ​​klasa PPAD jest trudna do rozwiązania? Gdyby istniał algorytm …

32 cc.complexity-theory  complexity-classes  gt.game-theory  conditional-results 

Wokół jest mnóstwo problemów z kompletnym NP i źródła je zbierające, np. Patrz książka Garey i Johnsona. Byłbym również zainteresowany, aby zobaczyć listę problemów uzupełniających NEXP. Czy jest dostępny? Ponieważ zakładam, że nie ma, otwieram to pytanie (czy to ma być wiki społeczności? Nie wiem o tych rzeczach). W idealnym …

31 cc.complexity-theory  complexity-classes  big-list  nexp 

Jakie byłyby paskudne konsekwencje NP = PSPACE? Dziwi mnie, że nie znalazłem nic na ten temat, biorąc pod uwagę, że zajęcia te należą do najbardziej znanych. W szczególności, czy miałoby to jakiekolwiek konsekwencje dla klas niższych?

30 cc.complexity-theory  complexity-classes  conditional-results 

Załóżmy, że P = NP jest prawdziwe. Czy byłoby zatem jakieś praktyczne zastosowanie do budowy komputera kwantowego, takie jak szybsze rozwiązywanie określonych problemów, czy też takie ulepszenie byłoby nieistotne w związku z faktem, że P = NP jest prawdziwe? Jak scharakteryzowałbyś poprawę wydajności, która nastąpiłaby, gdyby komputer kwantowy mógł zostać …

29 cc.complexity-theory  complexity-classes  quantum-computing 

Przypuszcza się, że ponieważ odwrotność oznaczałaby . Twierdzenie Ladnera stwierdza, że ​​jeśli a następnie . Wydaje się jednak, że dowód nie uogólnia na więc możliwość ie wydaje się otwarty.NP⊈P/polyNP⊈P/poly\mathsf{NP} \nsubseteq \mathsf{P}/\text{poly}PH=Σ2PH=Σ2\mathsf{PH} = \Sigma_2P≠NPP≠NP\mathsf{P} \ne \mathsf{NP}NPI:=NP∖(NPC∪P)≠∅NPI:=NP∖(NPC∪P)≠∅\mathsf{NPI} := \mathsf{NP} \setminus(\mathsf{NPC} \cup \mathsf{P}) \ne \emptysetP/polyP/poly\mathsf{P}/\text{poly}NPI⊂P/polyNPI⊂P/poly\mathsf{NPI} \subset \mathsf{P}/\text{poly}NP⊂NPC∪P/polyNP⊂NPC∪P/poly\mathsf{NP} \subset \mathsf{NPC} \cup \mathsf{P}/\text{poly} Zakładając, że …

29 cc.complexity-theory  complexity-classes  advice-and-nonuniformity  p-vs-np  np-intermediate 

Logarytmiczna jednolita NC jest zawarta w deterministycznej przestrzeni polilogu (czasami zapisywanej jako PolyL). Czy RNC o jednolitej przestrzeni logów również należy do tej klasy? Standardowa losowa wersja PolyL powinna być w PolyL, ale nie widzę, aby (jednolity) RNC był w randomizowanym-PolyL. Trudność, jaką widzę, polega na tym, że w RNC …

28 complexity-classes  randomized-algorithms 

Czytając artykuł „Czy nadszedł czas, aby zadeklarować zwycięstwo w liczeniu złożoności?” na blogu „Godel's Lost Letter and P = NP” wspominali o dychotomii CSP. Po kilku linkach, googlowaniu i wikipedii natknąłem się na twierdzenie Ladnera : Twierdzenie Ladnera: jeśli , wówczas występują problemy w , które nie są -kompletne.P≠NPP≠NP{\bf P} …

27 cc.complexity-theory  np-hardness  complexity-classes  sat  csp 

Parzystość-L jest zestawem języków rozpoznawanych przez niedeterministyczną maszynę Turinga, która może jedynie rozróżniać między liczbą parzystą lub nieparzystą liczbą ścieżek „akceptacji” (zamiast zerowej lub niezerowej liczby ścieżek akceptacji), i która jest dodatkowo ograniczone do pracy w przestrzeni logarytmicznej. Rozwiązanie liniowego układu równań powyżej ℤ 2 jest kompletnym problemem dla parzystości-L, …

27 cc.complexity-theory  complexity-classes  conditional-results 

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 dowodzą, że w przypadku problemów Õ który jest N …

26 cc.complexity-theory  reference-request  complexity-classes 

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 prawdopodobne, aby , zobaczył odpowiedzi na to …

26 cc.complexity-theory  complexity-classes  logspace 

Jakie byłyby konsekwencje #P = FP? Interesują mnie zarówno praktyczne, jak i teoretyczne konsekwencje. Z praktycznego punktu widzenia szczególnie interesują mnie konsekwencje dla sztucznej inteligencji. Wskaźniki do dokumentów lub książek są mile widziane. Nie mów, że #P = FP oznacza P = NP, już to wiem. Nie mów też: „nie …

26 cc.complexity-theory  ds.algorithms  complexity-classes  counting-complexity  ai.artificial-intel 

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ą …

26 cc.complexity-theory  complexity-classes  np 

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ą spełnione i że możemy zdecydować, czy funkcja docelowa w (lub innej „twardej” klasie złożoności) ma …

25 cc.complexity-theory  complexity-classes  circuit-complexity  gct  barriers 

Cześć chłopaki, rozumiem, że sztuczka dopełniania pozwala nam tłumaczyć klasy złożoności w górę - na przykład . Wypełnianie polega na „nadmuchiwaniu” danych wejściowych, uruchamianiu konwersji (powiedzmy od powiedzmy na ), co daje „magiczny” algorytm, który można uruchomić na wypełnionym wejściu. Chociaż ma to sens techniczny, nie mogę zrozumieć, jak to …

25 cc.complexity-theory  complexity-classes  padding 

Jest to związane z pytaniem Czy rozmiar członkostwa świadka dla każdego języka NP jest już znany? Niektóre naturalne problemy (-kompletne) mają świadków o długości liniowej: zadowalające przypisanie dla , ciąg wierzchołków dla itp.NPNP\mathsf{NP}SATSATSATHAMPATHHAMPATHHAMPATH Rozważ klasę złożoności „ ograniczoną do świadków o długości liniowej”. Formalna definicja tej klasy złożoności, nazwij ją …

24 cc.complexity-theory  complexity-classes  np