Co jest

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. $\mathsf{NP}$ $SAT$ $HAMPATH$

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ą : jeśli . $\mathsf{NP}$ $\mathcal{C}$ $L\in\mathcal{C}$ $\exists L'\in\mathsf{P}\colon (x\in L \iff \exists w\in\{0, 1\}^{O(|x|)}\colon (x, w)\in L')$

Czy to znana klasa złożoności? Jakie są jego właściwości?

cc.complexity-theory complexity-classes np argentpepper
źródło

Czy nie zawsze możesz to osiągnąć przez wypełnienie?

MCH

Jak zauważył MCH, jeśli

jest dowolnym językiem

ze świadkami o wielkości

, to

jest językiem

ze świadkami o wielkości liniowej, a

są wielomianowymi odpowiednikami wielokrotności jeden raz. Twoja klasa nie jest całkiem

L

$L$

N P

$\mathsf{NP}$

O (n^{k})

$O(n^k)$

p a d (L) := {x 10^{| x |^{k}} : x \in L}

$pad(L) := \{ x10^{|x|^{k}} : x \in L\}$

N P

$\mathsf{NP}$

L

$L$

p a d (L)

$pad(L)$

N P

$\mathsf{NP}$ , ale w zasadzie to samo. Klasa proponujesz nie jest zamknięta pod polytime wiele -on redukcje, ale dla każdego

istnieje jakiś język w swojej klasie, która jest polytime wielu jeden odpowiednik

L

$L$

N P

$\mathsf{NP}$

L

$L$

Joshua Grochow

Odpowiedzi:

Klasa proponujesz nie jest chyba . (Jeśli , to każdy język miałby świadków wielkości liniowej, co oznaczałoby, że każdy i , między innymi) . ${\cal C}$ $NP$ ${\cal C} = NP$ $NP$ $NP \subseteq TIME[2^{O(n)}]$ $NP \neq EXP$

Rozważanie takich klas jest bardzo naturalne; powstają w kilku ustawieniach. W tym artykule Rahul Santhanam (domyślnie) zaproponował notację dla obliczenia czasu za pomocą bitów domyślnych . Stąd . W tym artykule $TIGU(t(n),g(n))$ $t(n)$ $g(n)$ ${\cal C} = \bigcup_{k} TIGU(n^k,kn)$ , Zdefiniowałem analogiczną klasę . (NTIBI oznacza „niedeterministyczny czas i bity”.) Ponadto Cai i Chen nazywają Twoją klasę (GC oznacza „Zgadnij i sprawdź”, por. L. Cai i J. Chen SIAM Journal on Computing, 1996). Wreszcie, jeśli szukasz „ograniczonego niedeterminizmu”, możesz znaleźć jeszcze trzy notacje dla tej samej klasy ... $NTIBI[t(n),b(n)]$ $GC(O(n), P)$

Ryan Williams
źródło