[tl;dr]
Много известно, и это очень активная область! [/tl;dr]
Важно указать представление входных полиномов, так как если они заданы в виде списков коэффициентов или ненулевых мономов, задача тривиальна. Таким образом, обычно предполагается, что многочлены задаются как арифметические схемы (так называемые прямолинейные программы). И общий случай фактически сводится к проверке, является ли данный полином нулевым полиномом.
Есть две основные настройки, которые были изучены: случай «белого ящика», в котором один имеет арифметическую схему и может его осмотреть, и случай «черного ящика», в котором кто-то знает о схеме (размер, формальная степень, ...), но не может проверить его, оценить только по некоторым значениям.
Вот некоторые из ограничений на схемы, которые были изучены:
- Ограниченная глубина. Глубина контура - это самый длинный путь от входа до выходного затвора. Тестирование схем глубины23434
- Верхний / нижний разветвление: Для цепей с ограниченной глубиной было доказано много результатов, когда разветвление (или арность, то есть количество входов в данный затвор) либо верхнего затвора, либо нижнего затвора ограничено.
- Также были изучены другие ограничения, такие как ограничение количества использований переменной.
Этот опрос, проведенный Nitin Saxena, является хорошим источником для этих результатов. Обратите внимание, что ему уже больше года (!), И это очень активная область. Таким образом, самые последние результаты не покрыты.
Наконец, есть связь между дерандомизацией PIT и дерандомизацией других проблем: