Разрушается в предположении, что

13

Известно , что если NPP/Poly то многочлен иерархии коллапсирует Σ2P и MA=AM .

Какие самые сильные коллапсы могут произойти, если ?NEXPP/Poly

Springberg
источник
Это на самом деле « если известно , что то многочлен иерархия разрушается на» O 2NPP/poly2P .

Ответы:

14

Я считаю , что самым сильным является то , что . Это доказали Импальяццо Кабанец и Вигдерсон.NEXP=MA

См. Https://scholar.google.com/scholar?cluster=17275091615053693892&hl=en&as_sdt=0,5&sciodt=0,5.

Мне также было бы интересно узнать о более сильных провалах, чем этот.

Редактировать (8/24): Хорошо, я подумал о некотором потенциально более сильном крахе, который по существу следует из доказательств вышеупомянутой связанной статьи. Поскольку подразумевает N E X P = E X P (см. Ссылку выше) и E X P является замкнутым относительно дополнения, мы также имеем N E X P, замкнутое относительно дополнения, и, следовательно, N E X P = M A c o M ANEXPP/polyNEXP=EXPEXPNEXPNEXP=MAcoMA, который немного сильнее. Действительно, гипотеза предполагает , что для любого языка, А одна строка свидетель ш п может быть использован в соответствующем протоколе MA для всех YES-экземпляров какой - либо заданной длины п , так и N E X P = O M A c o O M A (где O M A = "Забывчивый MA", см. Fortnow-Santhanam-me http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.156.3018&rep=rep1&type=pdfNEXPwnnNEXP=OMAcoOMAOMA). Эти дополнительные свойства, хотя и технические, могут оказаться полезными в некоторых аргументах нижней границы схемы.

Редактировать 2: Похоже, Эндрю Морган уже подчеркнул это. Упс :)

Райан Уильямс
источник
15

Происходит много забавных вещей. Большинство из тех, что я знаю, начинаются с газеты IKW . Там NEXP=MA коллапс NEXP = MA , и (я думаю) это самый сильный буквальный коллапс классов сложности, которые мы знаем. Есть и другие виды «обвалов», хотя я думаю, что на это следует обратить внимание.

Наиболее важным, я думаю, является свойство "универсального сжатого свидетеля" (также из статьи IKW). С одной стороны, он дает вам инструмент, из которого многие другие провалы являются прямыми последствиями; во-вторых, последние нижние границы схемы (например, здесь и здесь ) для NEXP используют это соединение. Вкратце, свойство говорит о том, что для каждого NEXP языка L и любой NEXP машины M решающей L , каждый xL имеет кратко описываемый свидетель в соответствии с M, так что для каждого x LM . Формально существует полиномp зависимости отMxL существует схема Cx размера p(|x|) так что таблица истинности Cx является последовательностью недетерминированных выборов для M которые приводят к принятию на входе x .

Краткость свидетелей пригодится, потому что вы можете легко извлечь из нее множество других провалов. Например, тривиально следует, что NEXP=coNEXP=EXP . Например, предположим , что L в NEXP через NEXP -machine M . Свойство краткого свидетеля говорит, что есть многочлен p так что у M есть краткие свидетели размера p . Затем мы можем определить L в EXP , введя на входе x , перебор всех цепей размером не более p(|x|) и проверить, кодируют ли они последовательность вариантов выбора, которые приводят кM принятию на входе x . Вы можете объединить это с (ранее известным из интерактивных доказательств) результатом, что EXPP/polyEXP=MA для заключенияNEXPP/polyNEXP=MA .

Стоит подчеркнуть, что мы можем выбрать M и, следовательно, форму свидетелей. Например, из « NEXP есть универсальные сжатые свидетели» можно сделать вывод, что NEXP=OMA=co-OMA . Здесь OMA - «забывчивый-MA», что означает, что существует честный Мерлин, который зависит только от длины ввода. Легко видеть, что OMAP/poly , поэтому в основном это просто дает нормальную форму для того, как языки NEXP вычисляются в P/poly при условии, что NEXPP/polyна первом месте. Вот один из способов увидеть крах OMA :

For a language LNEXP decided by a machine M, construct a NEXP machine M as follows. View the n-bit input as a number N between 1 and 2n. For every x of length n, guess a witness wx and run M(x,wx) to verify it. M(N) accepts if and only if M accepts for at least N values of x. The guesses are arranged such that a succinct description of a witness for M is a circuit C which computes the map (x,i) the i-th bit of wx. Now suppose that N is precisely the number of strings in L at length n. Then succinct witnesses for M on input N are circuits that simultaneously encode all of M's witnesses for length-n inputs. In particular, if M has succinct witnesses, then all of M's witnesses can be simultaneously described by the same circuit.

To complete the claim, we'll recall that NEXP=PCP[poly,poly]. Letting M be the machine which guesses the PCP and then deterministically simulates the verifier, the above paragraph tells us the existence of simultaneously succinctly describable PCPs for every language in NEXP. So now to get NEXP=OMA, we have Merlin send the succinct description of the PCPs for all inputs of the current input length, which Arthur can check by just plugging in his input and then running the PCP verifier.

[Thanks to Cody Murray for pointing out the trick of using the input to count the number of strings in L. Previously I had M use that if NEXPP/poly then NEXP=EXP to write down the truth table of L, but Cody's strategy is more elegant.]

As a final note, while technically implied by NEXP=MA, the collapse NEXP=PSPACE has another interesting implication. It's known that PSPACE has a complete language which is both downward self-reducible as well as random self-reducible. Ordinarily, all such languages sit inside PSPACE and so we shouldn't hope to say (unconditionally) that NEXP has such a complete language as long as we hope that NEXPPSPACE. However, if NEXP=PSPACE, then NEXP does have such complete languages. A similar statement (replacing NEXP by EXP) was used by Impagliazzo and Wigderson to conclude a sort of "derandomization dichotomy" for BPP in relation to EXP, so it may be useful in discovering other consequences of NEXPP/poly.

Andrew Morgan
источник
BTW, don't trust citeseer to have the most recent (or even the best-rendered) versions of my papers. Here's better :) web.stanford.edu/~rrwill/projects.html
Ryan Williams
Thanks for the advice! I'll keep it in mind for the future (and that it likely applies to other authors as well).
Andrew Morgan