Czy

Pomyślałem, że podzielę się tym pytaniem, ponieważ może być interesujące dla innych użytkowników tutaj.

Załóżmy, że funkcja, która jest klasą jednolitej (jak ) jest także w niewielkim klasy nierównomierne (jak , czyli niejednolity ), czy to oznacza, że funkcja ta jest zawarta w mniejsza jednolita klasa (jak )? Jeśli odpowiedź na to pytanie jest pozytywna, jaka jest najmniejsza jednolita klasa złożoności, która zawiera ? Jeśli negatywne, czy możemy znaleźć interesujący naturalny kontrprzykład? $NP$ $AC^0/poly$ $AC^0$ $P$ $NP \cap AC^0/poly$

Czy zawarty w ? $AC^0/poly \cap NP$ $P$

Uwaga: znajomy już częściowo odpowiedział na moje pytanie offline, dodam jego odpowiedź, jeśli sam tego nie doda.

Pytanie to moja druga próba sformalizowania następującego nieformalnego pytania:

Czy niejednorodność może pomóc nam w obliczeniu naturalnych problemów z jednolitością?

Związane z:

Czy kwalifikuje się do naturalnych problemów w ? $P/poly−P$

cc.complexity-theory circuit-complexity uniformity Kaveh
źródło

@Kaveh: Być może ciekawym pytaniem byłoby zadać naturalny problem w P / poly i NP, ale nie w P. (A może to zbyt łatwe?)

Robin Kothari,

@Robin: Wydaje się, że jest interesująca, ale nie jestem pewien, że byłoby łatwiej znaleźć naturalną problem w

N P \cap P / p o l y - P

$NP \cap P/poly - P$

Kaveh

N E X P \neq E X P

$NEXP \neq EXP$

N T i m e (f) \neq D T i m e (f)

$NTime(f) \neq DTime(f)$

f

$f$

A C^{0} / p o l y

$AC^0/poly$

n

$n$

n

$n$

@Kaveh: Być może warto przyjrzeć się klasie YP, zdefiniowanej przez Scotta Aaronsona. To jest jak P / poly, ale „rada” nie jest zaufana. Innymi słowy, to jest jak NP przecina coNP, ale świadek może zależeć tylko od długości wejściowej. YP jest w P / poli i jest klasą jednolitą. Być może problem w YP, ale nie w P, jest przykładem problemu, którego szukasz. Byłoby to naturalne, jednolite, nie w P, w P / poli i być może niebanalne, ponieważ rada musi zostać zweryfikowana przez obwód.

Robin Kothari,

@Kaveh: Klasa YP („czas wielomianowy Yody”) jest bardziej formalnie zdefiniowana w pracy Scotta „The Learnability of Quantum States” [quant-ph / 0608142]

Alessandro Cosentino,

Odpowiedzi:

$\Lambda \in NE \setminus E$ $L = \{x : |x| \in \Lambda\}$ $\Lambda \in NE \setminus E$ $L \in NP \setminus P$ $L \in AC^0/poly$

Yuval Filmus
źródło

Dobra odpowiedź, Yuval!

Dai Le

Zasadniczo ta sama transformacja została zastosowana w Księdze 1974, aby pokazać, że E ≠ NE wtedy i tylko wtedy, gdy NP ∖ P zawiera język tally.

Tsuyoshi Ito

| x |

$|x|$

x

$x$

x

$x$

| x |

$|x|$

| x |

$|x|$

| x |

$|x|$

Λ

$\Lambda$

Odpowiedz na pierwsze pytanie: wydaje się mało prawdopodobne.

$NP \cap AC^0/poly \subseteq P$ $NEXP = EXP$

$C$ $C$ $C(0^n) C(0^{n-1}1) C(0^{n-2}10) \cdots C(1^n)$

$C$ $n$ $NEXP$

Teraz rozważ język

$L =$ $1^n |$ $n$

$L$ $AC^0/poly$ $1^n$ $L$ $n$

$L$ $NP$ $n$ $\log n$ $O(n)$ $O(n)$

$L \in P$ $NEXP=EXP$ $O(n^c)$ $\log n$

Twoje drugie pytanie jest szeroko otwarte (i otwarte).

Ryan Williams
źródło

Dlaczego musisz wziąć jakiś kompletny problem?

Yuval Filmus

Pomyślałem, że łatwiej jest podążać za argumentem.

Ryan Williams

Dziękuję Ryan za miłą odpowiedź i wyjaśnienie. Myślę, że nie miałbyś nic przeciwko, jeśli zaakceptuję odpowiedź Yuvala, mimo że byłeś pierwszą osobą, która opublikowała.

Kaveh

Na pytanie Kaveha „Czy niejednorodność może nam pomóc w obliczeniu naturalnych problemów z jednolitością?”

$n$ $1$ $n$ $n^5$ $n$

Referencje:

Friedhelm Meyer auf der Heide, „ Algorytm liniowego wyszukiwania wielomianowego dla problemu n-wymiarowego plecaka ”, 1984

Stasys
źródło

n

$n$

2

$2$

2^{n}

$2^n$

1

$1$

N P \subseteq P / p o l y

$NP\subseteq P/poly$

@Kaveh: Ale sama NP jest dużą OR LUB „Wersją czasową” P vs. NP jest: czy możemy zastąpić tę dużą OR przez deterministyczne algebraiczne drzewo decyzyjne o wielomianowej głębokości (z P na liściach)? Przypomnij sobie, że trywialna głębokość dla sumy częściowej wynosi 2 ^ n (nie n). Dopkin i Lipton (1978) wykazali, że głębokość n ^ 2/2 jest konieczna i powszechnie uważano, że można ją poprawić do n ^ k dla dowolnego k. Mayer auf der Heide obalił to przekonanie: wystarczy k = 5. Zatem niejednolitość MOŻE pomóc, jeśli interesuje nas głębokość (czas).

Stasys,