Учитывая , таким образом, что коэффициенты р , д ограничены B , имеет р ≡ Q удержание ?
Здесь применима лемма Шварца-Циппеля, поскольку она справедлива для общих полей и и для этой задачи существует эффективный рандомизированный алгоритм.
Мы ожидаем, что эта проблема будет иметь эффективную дерандомизацию.
Каковы последствия, если эта проблема не имеет эффективной дерандомизации?
big-picture
derandomization
conditional-results
Андраш Саламон
источник
источник
Ответы:
источник
Вы задаетесь вопросом о больших проблемах картины здесь. Натуральное число может быть канонически представлено в унарной записи, но это представление весьма неэффективно в пространстве. Вы также можете представить его в двоичной нотации, которая более экономична, но больше не канонична, поскольку вы также можете использовать десятичную или десятичную нотацию. Но обратите внимание, что представление схемами не намного менее эффективно, чем двоичная запись, см., Например,
И обратите внимание, что
(...)*(1+1)
это можно заменитьx:=(...) in x+x
, так что вам даже не нужно умножение для этого. Но поскольку у вас есть умножение, вы можете даже эффективно представлять числа, такие как1011^101101
. Также обратите внимание, что вы можете эффективно добавлять, вычитать и умножать числа в этом представлении. Но это представление не ограничивается числами, оно даже работает точно так же для многомерных полиномиальных функций. А для полиномов это даже вполне естественное представление, поскольку полиномы являются свободной алгеброй для коммутативных колец, и представление в виде схемы можно использовать для любой свободной алгебры.Вернуться к полиномам и схемным представлениям свободных алгебр. Вот несколько вопросов с картинками:
-> Да, проверка тождества для свободной алгебры для регулярных коммутативных колец является NP-полной. Давно не замечал, смотри ниже ...
Я особенно интересно о свободной алгебре для регулярных коммутативных колец здесь (то есть кольца с обобщенной обратной операцией), так как они позволили бы представлять рациональные числа и рациональные функции. Обратите внимание, что если бы мы использовали это представление только для чисел, то мы могли бы задаться вопросом, можем ли мы эффективно проверить
a < b
это представление. Этот вопрос не имеет смысла для свободного коммутативного кольца, но он может иметь смысл для многочленов, если мы интерпретируем их в контексте свободных частично упорядоченных колец. Но частично упорядоченное кольцо - это только реляционная структура, а не алгебра, так что это другой тип вопроса ...С другой стороны, я также считаю, что вы можете просто использовать любой разумный генератор псевдослучайных чисел и тем самым решить PIT для всех практических целей, если вы просто тестируете достаточно долго. Я только верю, что вы никогда не сможете избавиться от оставшихся (бесконечно малых) сомнений, подобных наборам нулевой меры, которые остаются раздражающими, будучи не пустыми.
источник