Существует ли эффективный алгоритм эквивалентности выражений?

14

например, ?xy+x+y=x+y(x+1)

Выражения взяты из обычной школьной алгебры, но ограничены арифметическим сложением и умножением (например, ), без инверсий, вычитания или деления. Буквы являются переменными.2+2=4;2.3=6

Если это поможет, мы можем запретить любое выражение, представляемое с числовыми значениями, отличными от ; т.е. не х 2, ни 3 х, ни 4 :1x23x4

  • полилинейный , нет степеней, отличных от : x + x y x 1 + x 1 y 1 в порядке, но не x 2 + x 3 y 4 , и не все, что может быть представлено в этом виде, как в полном разложении для суммирования -произведений, например, не x ( x + y ) x 2 + y ; 1x+xyx1+x1y1x2+x3y4x(x+y)x2+y
  • все одно , без коэффициентов, кроме : x + x y 1. x + 1. x y в порядке, но не 2 x + 3 x y , и не все, что может быть представлено так, как в полном раскрытии сумма-оф-продукты , например , не более ( х + у ) + х ( + б ) 2 х + у + Ь х ; и 1x+xy1.x+1.xy2x+3xya(x+y)+x(a+b)2ax+ay+bx
  • нет констант, кроме : опять же, в полностью расширенной сумме произведений, например, не ( a + 1 ) + ( b + 1 ) a + b + 21(a+1)+(b+1)a+b+2

Существует ли эффективный алгоритм для определения эквивалентности двух выражений?Q.


Для иллюстрации приведем неэффективный алгоритм грубой силы с экспоненциальным временем:

полностью разверните оба выражения до суммы продуктов , которую можно легко проверить на эквивалентность (просто игнорируйте порядок, так как коммутировать / связать можно переупорядочить).

например,
a ( x + y ) + b ( x + y ) a x + a y + b x + b y(a+b)(x+y)ax+ay+bx+by
a(x+y)+b(x+y)ax+ay+bx+by


Это кажется общеизвестной проблемой - даже старшеклассников учат ручным способам ее решения. Это также решается автоматическими средствами проверки / проверки теорем, но они концентрируются на более сложных аспектах.

Вот работающий онлайн-автомат для проверки теорем: http://tryacl2.org/ , который показывает эквивалентность, находя последовательность коммутирующих / ассоциированных / распространяющих и т. Д .:

? --- 188 шагов xy+x+y=x+y(x+1)
(thm (= (+ (* x y) x y) (+ x (* y (+ x 1))) ))

? --- 325 шаговy+x(y+1)=x+y(x+1)
(thm (= (+ y (* x (+ y 1))) (+ x (* y (+ x 1))) ))

Это мой первый вопрос здесь, поэтому, пожалуйста, дайте мне знать, если я выбрал не то место, неправильные теги, неправильный способ описания / запроса и т. Д. Спасибо!
NB: этот вопрос был переписан в ответ на комментарии.
Спасибо всем респондентам! Я многому научился.

hyperpallium
источник
3
Вопрос здесь нуждается в уточнении. В какой области вы работаете? Являются ли такие объекты, как " " и " b " в ваших выражениях элементами поля или переменных? На самом ли деле это поле (т. Е. Имеет ли обратное значение сложение и умножение)? Обратите внимание, что сумма продуктов не помогает, потому что ( a 1 + b 1 ) ( a 2 + b 2 ) ( a n + b n ) имеет экспоненциально много членов. ab(a1+b1)(a2+b2)(an+bn)
Дэвид Ричерби
4
Если объекты являются переменными, и вычитание разрешено, то вы, по сути, спрашиваете о проверке полиномиальной идентичности, которая имеет рандомизированный алгоритм полиномиального времени по лемме Шварца – Циппеля . тогда и только тогда, когда f ( x ) - g ( x ) = 0, и основная идея состоит в том, что многочлен, не равный нулю, не имеет много корней, поэтому, если вы начнете угадывать корни наугад и найти много корней, есть высокая вероятность того, что ваш полином был тождественно нулевым. f(x)=g(x)f(x)g(x)=0
Дэвид Ричерби
2
Я удивлен, что никто еще не упомянул об этом, но «если это в NP, мне не нужно беспокоиться о поиске полиномиального алгоритма», не имеет смысла. Каждая проблема в P также есть в NP. Вы, вероятно, хотели спросить, является ли проблема NP-полной (или -hard).
Том ван дер Занден
2
Если вы боретесь с основами, наши справочные вопросы могут быть вам полезны.
Рафаэль
2
@hyperpallium Прежде чем спрашивать, есть ли язык (то есть проблема решения) в NP, лучше, если вы поняли, что это значит. Возможно, справочные вопросы, на которые ссылался Рафаэль, помогли бы.
Юваль Фильмус

Ответы:

9

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

Все ваши выражения являются многомерными полиномами. Очевидно, ваши выражения построены по следующим правилам: (a) если является переменной, то x является выражением; (б) если с является константой, то с является выражением; (c) если e 1 , e 2 являются выражениями, то e 1 + e 2 и e 1 e 2 являются выражениями. Если это действительно то, что вы хотели, каждое выражение является многомерным полиномом над переменными.xxcce1,e2e1+e2e1e2

Теперь вы хотите знать, эквивалентны ли два выражения. Это равносильно проверке эквивалентности двух многомерных полиномов: при заданных значениях и p 2 ( x 1 , , x n ) вы хотите узнать, эквивалентны ли эти два полинома. Вы можете проверить это, вычтя их и проверив, тождественно ли результат равен нулю: definep1(x1,,xn)p2(x1,,xn)

q(x1,,xn)=p1(x1,,xn)p2(x1,,xn).

Теперь эквивалентны тогда и только тогда, когда q является нулевым полиномом.p1,p2q

Проверка, является ли тождественно нулевым, является проблемой нулевого тестирования для многомерных полиномов. Для этого есть эффективные алгоритмы. Например, одним из примеров алгоритма является оценка q ( x 1 , , x n ) при множестве случайных значений x 1 , , x n . Если вы найдете значение x 1 , , x n такое, что q ( x 1 , , x n ) , то вы знаете, что qqq(x1,,xn)x1,,xnx1,,xnq(x1,,xn)qне тождественно равен нулю, т. е. не эквивалентны. Если после многих испытаний все они равны нулю, можно сделать вывод, что q тождественно равно нулю (если q не тождественно равно нулю, вероятность того, что все эти испытания приведут к нулю, может быть экспоненциально мала). Количество итераций, которое вам нужно сделать, зависит от степени q ; см. литературу по тестированию полиномиальной идентичности для деталей.p1,p2qqq

Например, см. Https://en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel_lemma и http://rjlipton.wordpress.com/2009/11/30/the-curious-history-of-the- Schwartz-Zippel-лемму /

Эти алгоритмы применяются, если вы работаете над конечным полем. Вы не состояние , какое поле / кольцо вы работаете, и вы лечите эти выражения как формальные выражения ли (например, полиномы как абстрактные объекты) или как функции от . Если вы работаете над конечным полем, описанные выше методы применяются немедленно.FnF

rrZ/rZr

DW
источник
1
С другой стороны, было бы трудно доказать, что для каждого тождественно нулевого выражения существует не слишком длинное доказательство того, что выражение тождественно равно нулю.
@RickyDemer, отличный момент! Хорошее наблюдение. Я интерпретировал вопрос как вопрос о проверке эквивалентности, а не доказательстве, но это очень хорошее наблюдение. (Если вы хотите продемонстрировать доказательство эквивалентности на практике, я подозреваю, что такое доказательство выполнимо, если вы хотите сделать криптографические предположения, для некоторого определения «доказательства» - например, схема, которая достигает надежности в случайная модель оракула.)
DW
1
Благодарность! Я отношусь к ним как к формальным объектам, без инверсий, делений или вычитаний (но использую алгебру средней школы для этого вопроса; кажется, что он, скорее всего, уже решен). Вы имеете в виду, выбирайте большие случайные простые числари это обрабатывает выражения, как если бы они были конечными полями над базовым набором целых чисел [0 ..р-1]? В этой вики-ссылке сказано, что для этого нулевого тестирования нет известного субэкспоненциального детерминированного алгоритма. Вы знаете, относится ли это к моей проблеме?
Гиперпаллий
1
@ Hyperpallium, да, именно это я и имею в виду. Да, я верю, что это относится и к вашей проблеме. Вот почему я предложил рандомизированный алгоритм - существуют эффективные рандомизированные алгоритмы, хотя нет известных эффективных детерминированных алгоритмов.
DW
Как указано в комментарии выше, OP работает не в конечном поле, а на коммутативном полукольце. Это означает, что аддитивные инверсии не гарантируются, поэтому «вычитание» выражений для проверки равенства с нулем не является допустимой операцией.
Апнортон
0

Для того, чтобы следить на один мощности , один-Коэффициент и один-постоянных ограничений в вопросе:

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

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.

hyperpallium
источник