Problemy naturalne w

26

Czy występują jakieś naturalne problemy w , które nie są (wiadomo, że są / sądzi się, że są) w ? $NP \cap coNP$ $UP \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 jest w rzeczywistości w . $NP \cap coNP$ $UP \cap coUP$

— Joshua Grochow
źródło

Chociaż technicznie powinno to być wiki społeczności, ponieważ szukam listy, nie znam ŻADNYCH takich problemów, więc nie oczekuję więcej niż jednej odpowiedzi (a jeśli tak, to zasługuje na uznanie). Jeśli okaże się, że istnieje litania takich problemów, zmienię to na wiki społeczności.

— Joshua Grochow

2

Czy możesz zdefiniować UP lub podać link.

— Emil,

15

Chociaż wiadomo, że gry parzystości są w obu przypadkach, twierdzi się, że stochastyczne gry parzystości nie są znane w UP przecinają koUP.

— Lew Reyzin
źródło

Przyjmuję to jako „odpowiedź”, ponieważ jest to jedyna odpowiedź, która nie wiązała się z obietnicą problemów :). (Przepraszam, Andy.) Ponadto, chociaż osoby odpowiadające nie miały sposobu, aby to wiedzieć, właśnie tego szukałem, ponieważ zainspirowało mnie to pytanie po przeczytaniu odpowiedzi na inne pytanie: cstheory.stackexchange.com/questions/79/ … (Która dotyczyła gier z parzystością).

— Joshua Grochow

13

$L$ $R^n$ $\ell_2$ $L$ $t \in R^n$ $t$

$\cap$ $O(\sqrt{n})$

http://portal.acm.org/citation.cfm?id=1089025

$\cup$ $\cap$

$L$

$L$ $\leq 1$

$L$ $\leq C\sqrt{n}$ $C > 0$

$\cap$ $\cap$ $\setminus$ $\cap$ $\setminus$ $\neq$ $\Pi$ $L$ $\Pi$

— Andy Drucker
źródło

3

Bardzo interesujące! Myślę jednak, że „techniczność” klas obietnic jest bardzo istotna. Na przykład Valiant-Vazirani pokazuje, że PromiseUP jest NP-trudny przy randomizowanych redukcjach, ale wątpię, by coś takiego dotyczyło UP. (Rzeczywiście, jeśli VV można zdemandomizować i to prawda, mielibyśmy NP = UP. Oczywiście, nie ma wielu znanych złych konsekwencji NP = UP, ale wydaje się to mało prawdopodobne.)

— Joshua Grochow

1

Π

$\Pi$

Π

$\Pi$

Π

$\Pi$

7

$\cap$

— Lance Fortnow
źródło

3

Lance: czy masz wskaźnik, jak pokazać, że GI nie jest w GÓRZE, czy nie w trybie Co-UP? Nie jest dla mnie oczywiste, jak pokazać, że GI nie może być zredukowane do przestrzeni logicznej do GI ograniczonej do sztywnych grafów (tych bez nietrywialnych automorfizmów); istnieje prosta redukcja Turinga.

— András Salamon,

Nie znam żadnych interesujących konsekwencji GI w UP ani, co do tego, GI w P.

— Lance Fortnow

@ AndrásSalamon: Właśnie zauważyłem twój komentarz (sprzed kilku lat). Myślę, że jestem dzisiaj bardzo powolny, ale nie widzę „prostej redukcji Turinga” z GI do GI na sztywnych grafach. Czy mógłbyś opracować?

— Joshua Grochow

@JoshuaGrochow: Nie jestem teraz pewien szczegółów, ale myślę, że było to tylko odniesienie do jednego ze standardowych sposobów usztywnienia wykresów, na przykład zastąpienia każdej krawędzi odpowiednim gadżetem. Nie sądzę, że chciałem sugerować cokolwiek na temat tego, że jest wydajny .

— András Salamon,