[Recent Entries][Archive][Friends][User Info]
| July 17th, 2017 | |
|---|---|
| 02:12 pm [Link] |     Широко известна теорема Сильвестра-Галлаи утверждающая, что для любого конечного множества точек на плоскости, которые не лежат на одной на прямой можно найти такую прямую, которая будет проходит ровно через две точки из данного множества. Теорема знаменита тем, что несмотря на то, что её не могли доказать полвека, доказывается жутко элементарным образом, первое доказательство появилось в 1944-ом. Потом появились всякого рода её обобщения и вариации. Недавно выяснилось, что её можно применять для решения задачи Равенства нулю многочлена , т.е. для следующей алгоритмической задачи: дан многочлен от нескольких переменных (скажем, над целыми числами) в виде сумм и произведений всяких скобок, нужно выяснить, является ли он тождественным нулём. Раскрывать все скобки долго, а хочется полиномиального алгоритма. Существует вероятностный полиномиальный алгоритм - подставить в многочлен несколько случайных точек, если во всех них многочлен равен нулю, то он с большой вероятностью равен нулю тождественно - лемма Шварца-Зиппеля. Отметим, что вычислять значение многочлена в точке непосредственно эффективней чем сперва пытаться упрощать этот многочлен, а потом вычислять значение (а ёбанные училки в школах учат, что наоборот). Дико важным вопросом в теоретикал компьюта сцаенс является существование полиномиального детерминированного алгоритма для задачи Равенства нулю многочлена. В частных случаях это удаётся сделать, причём доказательство полиномиальности делается с применением обобщения теоремы Сильвестра-Галлаи. Чтобы похожий алгоритм годился для более широкого класса многочленов, хочется доказать аналог этой теоремы для более широкого класса объектов чем прямые. 
|