Czy rozmiar członkostwa świadka dla każdego języka NP jest już znany?

Pytanie przyszło mi do głowy, kiedy otrzymałem odpowiedź Dany Moshkovitz na inny temat .

Niech będzie językiem NP , a będzie odpowiednią relacją NP . Wiemy, że istnieje pewien wielomian taki, że: $L$ $R_L$ $p$

$\forall x \in L, \\, \exists w \in \\{0,1\\}^{p(|x|)} \quad (x,w) \in R_L$

Powyższe stwierdzenie wymaga tylko istnienia takiego , ale nie zmusza go do jednoznacznego ustalenia . Natomiast dla każdego znanego języka NP jest już znany: $p$ $p$

W przypadku SAT wielkość świadka jest równa liczbie atomów występujących we wzorze.
W przypadku Hamiltonicity wielkość świadka wynosi , gdzie jest zbiorem wierzchołków. $O(|V|)$ $V$
W przypadku wykresu 3-Kolorowanie wielkość świadka to , gdzie to zbiór wierzchołków. $O(|V|)$ $V$

Czy istnieje język NP (nawet sztuczny), dla którego wiemy, że istnieje jakiś wielomian ograniczający wielkość świadka, ale nie możemy jednoznacznie określić ? $p$ $p$

cc.complexity-theory np MS Dousti
źródło

Dla każdego języka w NP istnieje wiele relacji NP, które go powodują. Czy pytasz o języki których minimalny wielomian jest nieznany (to znaczy, gdzie możemy spróbować zminimalizować wielomian, patrząc na różne relacje, które powodują powstanie tego samego ), czy o relacje, w których odpowiadający wielomian jest nieznany (ale wiemy, że istnieje)?

L

$L$

p

$p$

L

$L$

p

$p$

Joshua Grochow

@Joshua: Mogę nie rozumieć twojego komentarza, ale jeśli znamy minimalne wszystkich relacji dla jakiegoś problemu z NP-zupełnym i jeśli nie jest to zero, czy to nie znaczy, że ?

p

$p$

P \neq N P

$P\neq NP$

Cong Han

@Cong: Masz rację. Chyba chodziło mi o minimalne p, jakie znamy , powiedzmy, z modulo standardowych założeń / aktualny stan techniki. Na przykład uważam, że artykuł STOC 2010 Ryana Williamsa pokazuje, że jeśli istnieje związek dla SAT z rozmiarem świadka , to , więc pokazanie takiej rzeczy jest poza obecnym zrozumieniem.

o (n)

$o(n)$

N E X P ⊈ P / p o l y

$NEXP \not\subseteq P/poly$

Joshua Grochow

@Joshua: Jasne, oczywiście! Mam to, dzieki.

Cong Han

Jeśli istnieje zależność dla obwodu SAT z rozmiarem świadka , gdzie jest liczbą wejść do obwodu, a jest rozmiarem obwodu, to tak, .

k - ω (\log n)

$k-\omega(\log n)$

k

$k$

n

$n$

N E X P ⊈ P / p o l y

$NEXP \not\subseteq P/poly$

Ryan Williams

Jeśli nie masz nic przeciwko sztucznym językom, możemy konstruować takie problemy przy użyciu praktycznie dowolnej liczby k, której wartość jest nieznana matematykom. Na przykład nie znamy wartości R (5,5) (piąta liczba Ramseya ) ani wielkości największej wykluczonej mniejszości z rodziny grafów bez węzłów (liczba ta jest skończona z powodu twierdzenia Robertsona-Seymour'a ) lub wartość BB (10), gdzie BB () oznacza funkcję Busy Beaver . Niech k równa się dowolnej z tych liczb. Wiemy, że k jest skończone, ale nie znamy wartości k.

Teraz skonstruuj jakiś problem w NP, gdy świadek ma rozmiar . Z czubka mojej głowy nie mogę wymyślić przyjemnego sposobu na zrobienie tego, ale jest jeden sposób. Niech dane wejściowe będą zwięzłym opisem wykresu. Ponieważ rozmiar opisu wynosi n, wykres ma wykładniczo wiele wierzchołków. (Na przykład, być może wejście jest obwodem, który akceptuje dwa wejścia x i y i mówi, czy (x, y) jest krawędzią na wykresie.) Pytanie polega na ustaleniu, czy wykres zawiera ścieżkę o długości . Ten problem występuje w NP, ponieważ przysłowia może wysyłać listę wierzchołków na ścieżce w kolejności, którą weryfikator może sprawdzić. Rozmiar świadka to . $O(n^k)$ $n^k$ $n^k$

Robin Kothari
źródło

Czy rozmiar członkostwa świadka dla każdego języka NP jest już znany?

Odpowiedzi: