Релятивизируют ли доказательства того, что перманент не является равномерным

Это продолжение этого вопроса и связано с этим вопросом Шивы Кинали.

Кажется, что доказательства в этих работах ( Аллендер , Кауссин-Маккензи-Териен-Фольмер , Койран-Перифель ) используют теоремы иерархии. Я хочу знать, являются ли доказательства « чистыми » теоремами диагонализации или они используют нечто большее, чем обычная диагонализация. Итак, мой вопрос

есть ли разумная релятивизация, которая помещает перманент в форму ?$\mathsf{TC^0}$

Обратите внимание, что я не уверен, как определить доступ к оракулу дляiform , я знаю, что найти правильное определение для классов небольшой сложности нетривиально. Другая возможность состоит в том, что перманент не является полным для в релятивизированной вселенной, и в этом случае я должен использовать вместо него некоторую полную проблему для в релятивизированной вселенной, и я думаю, что должен иметь полную проблему в любой разумной релятивизированной вселенной.$\mathsf{TC^0}$$\mathsf{\#P}$$\mathsf{\#P}$$\mathsf{\#P}$

Любое разделение классов, закрытых под «полиномиальными ресурсами», имеет оракула, делающего их равными. (Это при условии, что механизм оракула является справедливым и позволяет обеим моделям машин делать запросы полиномиальной длины и не более).

Пусть будет « T C 0 с воротами для оракула O ». Обозначая O как P S P A C E -полный язык при сокращениях T C 0 , мы имеем T C 0 O = P S P A C E = P S P A C E O = P P O , где в механизме оракула для П С $TC0^{O}$$TC0$$O$$O$$PSPACE$$TC0$$TC0^{O} = PSPACE = PSPACE^{O} = PP^{O}$ , мы рассчитываем использование пространства оракуловой лентой вместе с остальной памятью. (Таким образом, запрашиваются только полиномиальные запросы.) Такое равенство выполняется для многих классов, «закрытых по полиномиальным ресурсам», в том смысле, что они могут задавать полиномиальные запросы к оракулу, но не больше. Эти классы включают такие вещи, как A C 0 , T C 0 , L O G S P A C E (по другому механизму оракула, который не учитывает запросы оракула в направлении границы пространства), P , N P , P H и$PSPACE$$AC0$$TC0$$LOGSPACE$$P$$NP$$PH$ . Поэтому любое разделение классов в этом списке обязательно должно использовать некий «нерелятивизирующий» аргумент. Это также подразумевает (например), что естественные доказательства таких вещей, как четность не в A C 0, являются нерелятивизирующими (но это еще проще: все, что вам здесь нужно, это оракул для четности, поэтому вы получаете A C 0 [ 2 ] ).$PP$$AC0$$AC0[2]$

Я полагаю, что в совокупности доказательств, которые вы цитируете, большинство из них (если не все) работают, предполагая, что и получая противоречие. Результаты такого рода называются «косвенной диагонализацией». Так релятивизация их доказательство было бы сказать: «если T C 0 O = P P O , то противоречие ...» , но это предположение на самом деле верно для некоторых оракулов O .$TC0 = PP$$TC0^{O} = PP^{O}$$O$

В комментариях было указано, что как я использую его. Это просто тонкости с механизмом оракула. На стороне LOGSPACE лента запроса не может быть частью ограниченного пространства, поскольку запросы имеют полиномиальную длину. На стороне PSPACE, лента запроса является$LOGSPACE^{O} = PSPACE^{O}$берется как часть пространства, связанного. Это должно было сделать вещи "справедливыми". Но если вы дадите им точно такой же механизм оракула, тогда вы действительно сможете снова разделить их диагонализацией. Например, если запросы не учитываются в пределах пробела, то в PSPACE ^ {PSPACE} вы можете задавать экспоненциально длинные вопросы PSPACE, так что это фактически содержит EXPSPACE. Я прошу прощения за то, что не сказал это явно ранее.

Ограниченные в пространстве вычисления очень тонки по отношению к оракулам. Обратитесь к странице 5 этой статьи от Fortnow, чтобы получить хорошее представление о том, почему вычисления в Oracle и ограниченные пространства не всегда смешиваются.