Следствие PIT над

11

Учитывая , таким образом, что коэффициенты р , д ограничены B , имеет р Q удержание ?p(x1,,xn),q(x1,,xn)Z[x1,,xn]p,qBpq

Здесь применима лемма Шварца-Циппеля, поскольку она справедлива для общих полей и и для этой задачи существует эффективный рандомизированный алгоритм.ZQ

Мы ожидаем, что эта проблема будет иметь эффективную дерандомизацию.

Каковы последствия, если эта проблема не имеет эффективной дерандомизации?

Андраш Саламон
источник
1
Как будут и д дано?pq
@RickyDemer Как это дается в регулярном полиномиальном тестировании идентичности?
Не говорит ли результат Кабанец-Импальяццо о том, что мы не ожидаем эффективной дерандомизации?
Суреш Венкат
1
Да. Я подумал, что поднять это с помощью стандартного представления, разные строки представляют разные элементы.
3
@SureshVenkat: Kabanets & Impagliazzo доказали несколько вещей, в том числе: 1. Если PIT может быть дерандомизирован, либо NEXP не имеет полисайтовых (логических) схем, либо перманент не имеет полисайтовых (арифметических) схем; 2. Если для перманента требуются схемы суперпольного размера, PIT может быть «слабо» дерандомизирован. Поскольку выводы 1, как правило, предполагаются как и предпосылка 2, я бы сказал вопреки вам, что результат КИ говорит о том, что мы действительно ожидаем эффективной дерандомизации.
Бруно

Ответы:

8

coRPPRPPNPPBPPP=BPPE=DTIME(2O(n))

Джошуа Грохов
источник
Qpp{2,3,5,7,}{}
Действительно, как вы уже указывали, Schwarz-Zippel-DeMillo-Lipton применяется к произвольным полям, и все, что ему нужно, это ограничивать степень полиномов (не размер коэффициентов и не размер схемы). За очень небольшим числом исключений PIT обычно означает ограниченную по степени версию (степень, ограниченную полиномом по числу переменных).
Джошуа Грохов
Может быть глупо. Вы упомянули независимость от размера коэффициентов и размера схемы. Я предположил, что размер зависит от степени и размера коэффа. Я ошибся?
2
Размер схемы может зависеть от размера коэффициента, в зависимости от вашей модели (модель, от которой она зависит, обычно называется «без констант»). Размер схемы только очень слабо зависит от степени, в том смысле, что размер является, по крайней мере, логарифмом степени, но на самом деле алгоритм coRP, исходящий из SZDL, примерно равен степени. Это даже не зависит от функций, представляемых в виде цепей - просто в некоторой форме, в которой они могут быть легко оценены («черный ящик»).
Джошуа Грохов
Спасибо. Немного тревожно, что дерандомизацию можно проводить без потери эффективности, даже если сами коэффициенты могут быть конструктивно сложными
0

Вы задаетесь вопросом о больших проблемах картины здесь. Натуральное число может быть канонически представлено в унарной записи, но это представление весьма неэффективно в пространстве. Вы также можете представить его в двоичной нотации, которая более экономична, но больше не канонична, поскольку вы также можете использовать десятичную или десятичную нотацию. Но обратите внимание, что представление схемами не намного менее эффективно, чем двоичная запись, см., Например,

101101 = (((1+1)*(1+1)+1)*(1+1)+1)*(1+1)*(1+1)+1

И обратите внимание, что (...)*(1+1)это можно заменить x:=(...) in x+x, так что вам даже не нужно умножение для этого. Но поскольку у вас есть умножение, вы можете даже эффективно представлять числа, такие как 1011^101101. Также обратите внимание, что вы можете эффективно добавлять, вычитать и умножать числа в этом представлении. Но это представление не ограничивается числами, оно даже работает точно так же для многомерных полиномиальных функций. А для полиномов это даже вполне естественное представление, поскольку полиномы являются свободной алгеброй для коммутативных колец, и представление в виде схемы можно использовать для любой свободной алгебры.

c=1010101010c0cотказано, потому что большинство из этих чисел будет содержать больше информации, чем может быть представлено физической вселенной. Большая часть разглагольствования просто заставила меня смеяться, но этот момент заставил меня задуматься. Философы, такие как Уиллард Ван Орман Куайн, протестовали против утверждения о неактуализированных возможностях, среди прочего, потому что они приводят к беспорядочным элементам, которые нельзя осмысленно назвать идентичными самим себе и отличными друг от друга. Поэтому я счел вполне разумным задаться вопросом о представлениях чисел, для которых все еще выполняются сложение, вычитание и умножение, и, по крайней мере, содержательно определить, отличаются ли два числа друг от друга. Схема представления достигает этого ...

Вернуться к полиномам и схемным представлениям свободных алгебр. Вот несколько вопросов с картинками:


  • n4n
  • Существует ли свободная алгебра, для которой эффективное детерминированное тестирование идентичности лишает законной силы любые широко распространенные гипотезы, такие как P! = NP?
    -> Да, проверка тождества для свободной алгебры для регулярных коммутативных колец является NP-полной. Давно не замечал, смотри ниже ...
  • Z[x1,,xn]

Я особенно интересно о свободной алгебре для регулярных коммутативных колец здесь (то есть кольца с обобщенной обратной операцией), так как они позволили бы представлять рациональные числа и рациональные функции. Обратите внимание, что если бы мы использовали это представление только для чисел, то мы могли бы задаться вопросом, можем ли мы эффективно проверить a < bэто представление. Этот вопрос не имеет смысла для свободного коммутативного кольца, но он может иметь смысл для многочленов, если мы интерпретируем их в контексте свободных частично упорядоченных колец. Но частично упорядоченное кольцо - это только реляционная структура, а не алгебра, так что это другой тип вопроса ...


Здесь применима лемма Шварца-Циппеля, поскольку она справедлива для общих полей и Z ⊂ Q,ZQ

((33+3)3+x)3((22+5)3+x)2xn72n/253n/3ZB=exp(exp(n))O(logB)


Z[x1,,xn]

С другой стороны, я также считаю, что вы можете просто использовать любой разумный генератор псевдослучайных чисел и тем самым решить PIT для всех практических целей, если вы просто тестируете достаточно долго. Я только верю, что вы никогда не сможете избавиться от оставшихся (бесконечно малых) сомнений, подобных наборам нулевой меры, которые остаются раздражающими, будучи не пустыми.

Томас Климпел
источник
P!=NP
Я думаю только о проблеме свободной алгебры, но не о том, о чем вы думаете