например, ?
Выражения взяты из обычной школьной алгебры, но ограничены арифметическим сложением и умножением (например, ), без инверсий, вычитания или деления. Буквы являются переменными.
Если это поможет, мы можем запретить любое выражение, представляемое с числовыми значениями, отличными от ; т.е. не х 2, ни 3 х, ни 4 :
- полилинейный , нет степеней, отличных от : x + x y ≡ x 1 + x 1 y 1 в порядке, но не x 2 + x 3 y 4 , и не все, что может быть представлено в этом виде, как в полном разложении для суммирования -произведений, например, не x ( x + y ) ≡ x 2 + y ;
- все одно , без коэффициентов, кроме : x + x y ≡ 1. x + 1. x y в порядке, но не 2 x + 3 x y , и не все, что может быть представлено так, как в полном раскрытии сумма-оф-продукты , например , не более ( х + у ) + х ( + б ) ≡ 2 х + у + Ь х ; и
- нет констант, кроме : опять же, в полностью расширенной сумме произведений, например, не ( a + 1 ) + ( b + 1 ) ≡ a + b + 2
Существует ли эффективный алгоритм для определения эквивалентности двух выражений?
Для иллюстрации приведем неэффективный алгоритм грубой силы с экспоненциальным временем:
полностью разверните оба выражения до суммы продуктов , которую можно легко проверить на эквивалентность (просто игнорируйте порядок, так как коммутировать / связать можно переупорядочить).
например,
a ( x + y ) + b ( x + y ) → a x + a y + b x + b y
Это кажется общеизвестной проблемой - даже старшеклассников учат ручным способам ее решения. Это также решается автоматическими средствами проверки / проверки теорем, но они концентрируются на более сложных аспектах.
Вот работающий онлайн-автомат для проверки теорем: http://tryacl2.org/ , который показывает эквивалентность, находя последовательность коммутирующих / ассоциированных / распространяющих и т. Д .:
? --- 188 шагов
(thm (= (+ (* x y) x y) (+ x (* y (+ x 1))) ))
? --- 325 шагов
(thm (= (+ y (* x (+ y 1))) (+ x (* y (+ x 1))) ))
Это мой первый вопрос здесь, поэтому, пожалуйста, дайте мне знать, если я выбрал не то место, неправильные теги, неправильный способ описания / запроса и т. Д. Спасибо!
NB: этот вопрос был переписан в ответ на комментарии.
Спасибо всем респондентам! Я многому научился.
источник
Ответы:
Ваша задача сводит к нулю тестирование многомерных полиномов, для которых существуют эффективные рандомизированные алгоритмы.
Все ваши выражения являются многомерными полиномами. Очевидно, ваши выражения построены по следующим правилам: (a) если является переменной, то x является выражением; (б) если с является константой, то с является выражением; (c) если e 1 , e 2 являются выражениями, то e 1 + e 2 и e 1 e 2 являются выражениями. Если это действительно то, что вы хотели, каждое выражение является многомерным полиномом над переменными.x x c c e1,e2 e1+e2 e1e2
Теперь вы хотите знать, эквивалентны ли два выражения. Это равносильно проверке эквивалентности двух многомерных полиномов: при заданных значениях и p 2 ( x 1 , … , x n ) вы хотите узнать, эквивалентны ли эти два полинома. Вы можете проверить это, вычтя их и проверив, тождественно ли результат равен нулю: definep1(x1,…,xn) p2(x1,…,xn)
Теперь эквивалентны тогда и только тогда, когда q является нулевым полиномом.p1,p2 q
Проверка, является ли тождественно нулевым, является проблемой нулевого тестирования для многомерных полиномов. Для этого есть эффективные алгоритмы. Например, одним из примеров алгоритма является оценка q ( x 1 , … , x n ) при множестве случайных значений x 1 , … , x n . Если вы найдете значение x 1 , … , x n такое, что q ( x 1 , … , x n ) , то вы знаете, что qq q(x1,…,xn) x1,…,xn x1,…,xn q(x1,…,xn) q не тождественно равен нулю, т. е. не эквивалентны. Если после многих испытаний все они равны нулю, можно сделать вывод, что q тождественно равно нулю (если q не тождественно равно нулю, вероятность того, что все эти испытания приведут к нулю, может быть экспоненциально мала). Количество итераций, которое вам нужно сделать, зависит от степени q ; см. литературу по тестированию полиномиальной идентичности для деталей.p1,p2 q q q
Например, см. Https://en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel_lemma и http://rjlipton.wordpress.com/2009/11/30/the-curious-history-of-the- Schwartz-Zippel-лемму /
Эти алгоритмы применяются, если вы работаете над конечным полем. Вы не состояние , какое поле / кольцо вы работаете, и вы лечите эти выражения как формальные выражения ли (например, полиномы как абстрактные объекты) или как функции от . Если вы работаете над конечным полем, описанные выше методы применяются немедленно.Fn→F
источник
Для того, чтобы следить на один мощности , один-Коэффициент и один-постоянных ограничений в вопросе:
Они определяют подмножество проблемы проверки полиномиальной идентичности. Очевидно, что их можно решить с помощью методики, которая решает общую проблему. Вопрос в том, образуют ли они подмножество, которое легче решить.
one-coefficient: in problems without this, terms might be combined, making the problem easier. Consider the Binomial Theorem/Pascal's triangle for(a+b)n . This can be expanded one factor at a time, producing terms with overlapping orders e.g. (a+b)(a+b)=aa+ab+ab+bb=aa+2ab+bb The fewer terms make it easier to expand with the next factor: (aa+2ab+bb)(a+b)=aaa+2aab+abb+aab+2abb+bbb=aaa+3aab+3abb+bbb and again terms are combined, making a smaller simpler problem. This combining of terms is a form of dynamic programming.
That is, the possibility of combining terms, creating a non-one coefficient, makes the problem easier not harder.
(Although there is more work in calculation in multiplying non-one coefficients)
non-one constants are included in the above argument by considering constants as variables with zero exponent.
one-power I don't think this makes any difference. Although non-one exponents can be created in more than one way (e.g.a4=a2a2=a1a3 ), and this can lead to overlap and combination (as in the Binomial Theorm/Pascal's triangle above), actual combination is only possible if non-one coefficients are allowed.
The above is not a formal or rigorous argument. It rests on an assumption about what makes the problem difficult. But it does seem to me that combining terms only makes for an easier problem - so preventing this by the one coefficient constraint is not going to make the subset easier.
источник