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,