P / Poly против классов равномерной сложности

9

Не известно, содержится ли NEXP в P / poly. Действительно, доказательство того, что NEXP отсутствует в P / poly, может иметь некоторые применения в дерандомизации.

  1. Каков наименьший равномерный класс C, для которого можно доказать, что C не содержится в P / poly?

  2. Если бы показ, что со-NEXP не содержится в P / poly, имел бы другие теоретические последствия сложности, как в случае NEXP против P / poly?

Примечание: я знаю, что SP2 как известно, не содержится в Size[nk] для каждой фиксированной константы k(Это было также показано для МА с 1 небольшим советом). Но в этом вопросе меня не интересуют результаты для фиксированныхk, Я действительно заинтересован в классах, которые отличаются от P / Poly, даже если эти классы очень большие.

Springberg
источник
По сути, вы задаете проблему с нижними границами суперполиномиального размера для общих схем.
Каве
8
MAexp как известно, не быть в P/poly, Посмотрите статью в Википедии для краткого доказательства.
Робин Котари
4
P / poly замкнут под комплементом, поэтому он содержит NEXP тогда и только тогда, когда он содержит coNEXP.
Эмиль Йержабек
2
Эмиль, Робин и Эндрю, спасибо за ваши ответы. Я думаю, что мой вопрос можно считать ответом сейчас. Кто-нибудь напишет это в ответ, чтобы я мог принять это?
Спрингберг
2
я полагаю, что MAexpсамый маленький универсальный класс с известными суперполиномиальными нижними границами ( people.cs.uchicago.edu/~fortnow/papers/nonrel.pdf ), и этоOP2самый маленький с произвольными полиномиальными нижними границами ( citeseerx.ist.psu.edu/viewdoc/… ).
Алексей Головнев

Ответы:

9

Есть несколько результатов в литературе, утверждающих, что определенный класс C удовлетворяет CSIZE(nk) для любой kи, как правило, легко дополнить их, чтобы показать, что любая едва расширенная версия C не в P/poly,

Позвольте мне сказать, что f:NNявляется суперполиномиальной оценкой, если она конструируема по времени, иf(n)=nω(1), Например,nloglogloglognявляется суперполиномиальной оценкой. На самом деле, поучительное упражнение показывает, что еслиg(n) является любой неограниченной монотонной вычислимой функцией, существует суперполиномиальная оценка f такой, что f(n)ng(n),

Во-первых, прямая диагонализация показывает, что ΣP4SIZE(nk) для любой k, Тот же аргумент дает:

  • Если f любая суперполиномиальная оценка, то Σ4-TIME(f(n))P/poly,

    Эскиз доказательства: для любого n, позволять Cn быть лексикографически первой схемой размера 2f(n) которая вычисляет булеву функцию в n переменные не вычисляются по схеме размера <f(n), Тогда языкL определяется xLC|x|(x)=1 работает.

Хорошо известное улучшение утверждает, что S2PSIZE(nk) для любой k, Точно так же,

  • Если f любая суперполиномиальная оценка, то S2-TIME(f(n))P/poly,

    Эскиз доказательства: если нет, то в частности NPS2PP/polyотсюда PH=S2P, По дополнительному аргументу,Σ4-TIME(f(n))S2-TIME(f(n))P/polyнет.

Забывшие классы делают еще лучше. Принимая во внимание возражение, высказанное Апурвой Бхагаватом, давайтеNLin=NTIME(n), затемNLinO2PSIZE(nk) для любой kи тот же аргумент дает:

  • Если f любая суперполиномиальная оценка, то NLinO2-TIME(f(n))P/poly,

    Эскиз доказательства: если NLinP/polyзатем, набив, NPP/poly, что подразумевает PH=O2P, Затем мы продолжаем, как и раньше.

Есть также результаты с участием МА. Часто упоминаемый результат, которыйMA-EXPP/polyэто перебор. Шантанам оказался

promise-MApromise-coMASIZE(nk)
для любой kи аналогичный аргумент дает:
  • Если f любая суперполиномиальная оценка, то

    promise-MA-TIME(f(n))promise-coMA-TIME(f(n))P/poly.

    Эскиз доказательства: по лемме Сантханама 11 (которая является заостренной версией стандартного факта, что PSPACE=IP с PSPACE Prover), есть PSPACE-полный язык L и рандомизированный многократный оракул ТМ M такой, что на входе x, M только задает оракулу запросы длины |x|; еслиxL, тогда ML(x) принимает с вероятностью 1; и еслиxLтогда для любого оракула A, MA(x) принимает с вероятностью 1/2,

    Для подходящего монотонного полинома p, позволять A=(AYES,ANO) быть проблемой обещания, определенной

    (x,s)AYES(x,s)ANOcircuit C(p(|C|+|x|)f(|s|)Pr[MC(x) accepts]=1),circuit C(p(|C|+|x|)f(|s|)Pr[MC(x) accepts]1/2).
    Let h(x) be a polynomial reduction of L to its complement, and let B=(BYES,BNO) be the promise problem
    (x,s)BYES(x,s)BNO(x,s)AYES(h(x),s)ANO,(x,s)ANO(h(x),s)AYES.
    If p(n) is chosen suitably large,
    Bpromise-MA-TIME(f(n))promise-coMA-TIME(f(n)).
    So, let us assume for contradiction that B has polynomial-size circuits, say, BSIZE(nk). Let s(n) denote the size of the smallest circuit computing L on inputs of length n, and put t(n)=f1(p(s(n))); more precisely,
    t(n)=min{m:p(s(n))f(m)}.
    Then x(x,1t(n)) is a reduction of L to B, thus LSIZE(t(n)k), which means
    s(n)t(n)k.
    But since f is superpolynomial, we have t(n)=s(n)o(1). This gives a contradiction for n sufficiently large.

If we prefer a result with a non-promise version of MA, Miltersen, Vinodchandran, and Watanabe proved

MA-TIME(f(n))coMA-TIME(f(n))P/poly
for a half-exponential function f. We can improve it in two ways: first, it holds for 1k-exponential bounds for any constant k, and second, it holds for oblivious classes. Here, a 1k-exponential function is, roughly speaking, a function f such that ffk=exp. See the Miltersen–Vinodchandran–Watanabe paper and references therein for the precise definition; it involves a well-behaved family of well-behaved functions eα(x), αR+, such that e0(x)=x, e1(x)=ex1, and eα+β=eαeβ. Also, if f(n)eα(poly(n)) and g(n)eβ(poly(n)), then f(g(n))eα+β(poly(n)). Then we have:
  • OMA-TIME(eα)coOMA-TIME(eα)P/poly for any α>0.

    Proof sketch: Assume otherwise. Fix an integer k such that 1/k<α. Let me abbreviate

    OcOMT(f)=OMA-TIME(poly(f(poly(n)))coOMA-TIME(poly(f(poly(n))).
    By padding, we have
    OcOMT(eβ+1/k)SIZE(eβ(poly(n)))(1)
    for any β0. Moreover, using e.g. Santhanam’s Lemma 11 above, we have the implication
    PSPACESIZE(eβ(poly(n)))PSPACEOcOMT(eβ).(2)
    Since trivially PSPACEOcOMT(e1), a repeated application of (1) and (2) shows PSPACESIZE(e(k1)/k(poly(n))), PSPACEOcOMT(e(k1)/k), PSPACESIZE(e(k2)/k(poly(n))), PSPACEOcOMT(e(k2)/k), and so on. After k steps, we reach
    PSPACEP/polyandPSPACE=OMAcoOMA.
    Using padding once more, we get
    DSPACE(e1/k)OcOMT(e1/k)P/poly,
    which contradicts the results above, as e1/k is a superpolynomial bound.
Emil Jeřábek
источник
4

Since nobody posted an answer, I will answer the question myself with the comments posted in the original question. Thanks to Robin Kothari, Emil Jerabek, Andrew Morgan and Alex Golovnev.

MAexp seems to be the smallest uniform class with known superpolynomial lower bounds.

OP2 seems to be the smallest known class not having circuits of size nk for each fixed k.

By diagonalization, it follows that for any super-polynomial (and space-constructible) function s, DSPACE[s(n)] doesn't have polynomial-size circuits. PSPACE versus P/poly is still open.

P/poly is closed under complement, so it contains NEXP if and only if it contains coNEXP.

Springberg
источник
4

Please correct me if I'm wrong, but as far as I can tell, we actually don't know a fixed-polynomial size lower bound for OP2. This is because the usual Karp-Lipton argument doesn't go through for OP2, since we don't know whether NPOP2 (in fact, this is equivalent to asking whether NPP/poly). However, we do know that NPOP2 isn't contained in SIZE(nk) for any k, as shown by Chakaravarthy and Roy.

Apoorva Bhagwat
источник