Трудно выглядящие алгоритмические задачи, облегчаемые с помощью теорем

28

Я ищу хорошие примеры, где встречается следующее явление: (1) Алгоритмическая проблема выглядит сложной, если вы хотите решить ее, работая из определений и используя только стандартные результаты. (2) С другой стороны, это становится легко, если вы знаете некоторые (не очень стандартные) теоремы.

Цель этого состоит в том, чтобы проиллюстрировать студентам, что изучение большего количества теорем может быть полезным даже для тех, кто находится за пределами области теории (например, инженеры-программисты, компьютерные инженеры и т. Д.). Вот пример:

Вопрос: Даны ли целые числа , существует ли вершинный граф (и, если да, найти его), такой, что его вершинная связность равна , его краевая связность равна , а минимальная степень равна ?n,k,l,dк л дnkld

Обратите внимание, что мы требуем, чтобы параметры были в точности равны заданным числам, они не были просто границами. Если вы хотите решить это с нуля, это может показаться довольно сложным. С другой стороны, если вы знакомы со следующей теоремой (см. Теория экстремальных графов Б. Боллобаса), ситуация становится совершенно иной.

Теорема: Пусть целые числа. Существует вершинный граф с связностью вершин , связностью ребер и минимальной степенью , если и только если выполняется одно из следующих условий:н к л дn,k,l,dnkld

  • 0kld<n/2 ,
  • 12d+2nkl=d<n1
  • k=l=d=n1.

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

Можете ли вы привести дополнительные примеры в этом духе, где знание (не столь стандартной) теоремы значительно упрощает задачу?

Андрас Фараго
источник
1
Я не уверен, что полностью понимаю ваши вопросы. Пример, который вы приводите, является нетривиальной задачей, для которой Боллобас дал алгоритм (который подразумевает характеристику). Итак, у меня сложилось впечатление, что на вашем примере ответом будет любой нетривиальный алгоритм ...
Бруно,
3
Первичность и теорема АКС.
Ламин
@ Бруно: Я имею в виду, что алгоритмическая задача становится намного проще, если вы знаете теорему, которая не очень хорошо известна, поэтому, возможно, никто никогда не слышал о ней. Представленный пример не идеален в том смысле, что здесь теорема не только помогает, но и фактически решает проблему. Что я действительно ищу, так это когда теорема помогает, предоставляет некоторые полезные ярлыки, но не полностью решает проблему сама по себе.
Андрас Фараго
3
Сообщество вики?
Джошуа Грохов
1
Теорема Робертсона – Сеймура, также гипотезы, которые облегчают детерминированное нахождение простых чисел.
Kaveh

Ответы:

31

Решающий изоморфизм простых групп, заданный их таблицами умножения. Тот факт, что это может быть сделано за полиномиальное время, непосредственно вытекает из того факта, что все конечные простые группы могут быть порождены не более чем двумя элементами, и в настоящее время единственное известное доказательство этого факта использует Классификацию конечных простых групп (возможно, самую большую теорему). - с точки зрения авторов, статей и страниц - когда-либо доказано).

Джошуа Грохов
источник
3
Это отличный пример! Кстати, комментарии к этому ответу утверждают, что в некотором смысле эта теорема примерно такая же сложная, как и классификация: mathoverflow.net/a/59216/35733
Сашо Николов
32

Если я правильно понимаю ваш вопрос, каноническим примером будет решение, если у графа есть эйлерова схема: эквивалентно проверке связности G, и каждая вершина имеет четную степень.GG

Сашо Николов
источник
20

Сегодня днем ​​я читал « Стрингологию» - «настоящую» теорию струн .

Проблема: Если и y - две строки в некотором алфавите, когда есть некоторые натуральные числа m , n такие, что x m = y n .xym,nxm=yn

Теорема: Существуют натуральные числа такие, что x m = y n тогда и только тогда, когда x y = y x .m,nxm=ynxy=yx

Пратик Деогхаре
источник
9

Нахождение количества (различных) действительных корней вещественного многочлена, либо во всех ℝ, либо в заданном интервале. Теорема Штурма говорит вам, что последовательность полиномов, которая удовлетворяет небольшому числу требований, может быть использована для подсчета числа действительных корней многочлена с действительными коэффициентами.

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

Удивительно, но мало кто знает об этом результате, несмотря на то, что он довольно старый (1829 г.). Он используется во многих системах компьютерной алгебры, но все профессора математики в моем университете, которых я спросил, либо вообще не знают теорему Штурма, либо знают только ее по имени и что она имеет отношение к корням полиномов.

Большинство людей очень удивляются, когда вы говорите им, что что-то вроде точного подсчета настоящих корней так просто и не требует какого-либо приближения, учитывая, что найти корни гораздо сложнее. (Помните, что для полиномов степени ≥ 5 даже не существует «правильной» формулы для корней)

Мануэль Эберл
источник
9

Теорема: у каждого плоского графа есть вершина со степенью не более 5.

Задача: Разработать представление плоских графов, где мы можем проверить, является ли ( u , v ) ребром за O ( 1 ) время.O(n)(u,v)O(1)

Мы можем удалить вершину со степенью не более 5 и добавить ее в список в качестве ключа и его соседей в качестве значений. Оставшийся граф также плоский и имеет вершину со степенью не более 5. Таким образом, занимаемое пространство составляет не более . Мы можем проверить, есть ли u в списке смежности v ; если нет, мы можем проверить, находится ли v в списке смежности u . Это займет не более 10 шагов.5nuvvu10

Pratik Deoghare
источник
5
С немного большей осторожностью вы можете уменьшить размер списка, хранящегося в каждой вершине, до 3, а количество шагов для проверки смежности - до 6. См .: Планарные ориентации с низкой степенью выхода и уплотнение матриц смежности. М. Хробак и Д. Эппштейн. Теор. Комп. Sci. 86 (2): 243–266, 1991. ics.uci.edu/~eppstein/pubs/ChrEpp-TCS-91.pdf
Дэвид Эппштейн
7

Я думаю, что автором этой категории, по крайней мере, в том, что касается ассиметрии сложности, является следующая проблема:

Учитывая планарный граф , G 4-раскраска?GG

Теорема о четырех цветах упрощает алгоритм до return true.

Йонас Кёлкер
источник
6

Может ли реальный (многомерный) полином быть выражен в виде суммы квадратов вещественных полиномов, можно решить путем сведения к полуопределенному программированию. Нужно знать SDP и что SDP можно решить эффективно.p

Чандра Чекури
источник
5

Другой пример: для неориентированного графа имеет ли он минимальный разрез, в котором все ребра не пересекаются? Если так, найдите один.

На первый взгляд это может показаться сложным. Однако это становится легко, если вы знаете результат, что неориентированный вершинный граф может иметь не более n ( n - 1 ) / 2 минимальных сокращений, и все они могут быть перечислены за полиномиальное время.nn(n1)/2

Это может быть расширено до почти минимальных сокращений, которые больше минимального сокращения, но не более чем на постоянный коэффициент. Их число все еще ограничено полиномом.

(Я не искал ссылку, я помню, что эти результаты принадлежат Д. Каргеру.)

Андрас Фараго
источник
4

Проблема: сходимость формулы MSO (монадической логики второго порядка) над конечными словами.

Теорема: MSO эквивалентна конечным автоматам над конечными словами.

Выше можно поднять до бесконечных слов, конечных деревьев, бесконечных деревьев.

Денис
источник
4

Несколько более сложный пример: факторизация неотрицательной матрицы , когда неотрицательный ранг постоянен.

AMm×nUMm×kVMk×nA=UVA

O(r2)r

(mn)O(r2)UV(mn)o(r)

zotachidil
источник
4

Диффи Хеллман

(g,ga,gb,gc)gGgc=gab

При стандартных предположениях о твердости проблемы дискретного журнала эта проблема также может показаться сложной.

e(g,gc)=?e(ga,gb)

e:G×GGT

Подробнее об этом можно прочитать в «Решении проблемы Диффи-Хеллмана» , Boneh'98 или в Google Lookup на Pairings.

Subhayan
источник
3

(Тривиально) существование равновесия Нэша в конечной игре, четное число гамильтоновых путей в кубическом графе, различные типы неподвижных точек, прилично сбалансированные сравнения в частичных порядках и многие другие проблемы PPAD.

Йонатан Н
источник
Существование равновесия по Нэшу - и многие другие доказательства существования, которые характеризовали PPAD, - кажется, не облегчают алгоритмически ни одну из этих проблем ...
Джошуа Грохоу,
1
Я имел в виду вариант решения этих проблем.
Йонатан Н
2

((V,E),s,t)EEst(V,E)E

st(V,E)st

Максимум
источник
1
Можно сказать, что поток легко, если вы знаете, что LP легко. Таким образом, две большие теоремы (LP в poly time и maxflow-mincut) позволяют нам вычислять min-cut.
Чандра Чекури
@CandraChekuri, мое личное мнение таково, что это не совсем соответствует вопросу: теорема о том, что LP разрешима в polytime, не помогает нам на самом деле построить алгоритм для минимальных сокращений. Нам нужен фактический алгоритм LP.
Макс
На самом деле, нет. Если вы можете найти значение минимального среза в данном графике эффективно, то вы можете использовать такой алгоритм, чтобы найти сам фактический срез.
Чандра Чекури,
2

Вот еще один пример: если дан неориентированный простой граф, определите, есть ли у него две вершинно-непересекающиеся схемы.

23

3K5K3,n3

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

Примечания: (1) Доказательство теоремы совсем не легко. (2) После того, как мы решили, что существуют две непересекающиеся цепи, кажется менее ясным, как решить соответствующую проблему поиска , то есть, как на самом деле найти такие схемы. Теорема не дает прямого совета этому.

Андрас Фараго
источник
1

менее сложные примеры: некоторые теоремоподобные свойства показывают, что жадные алгоритмы для некоторых задач оптимальны. для непосвященного не совсем очевидно, что минимальное связующее дерево можно найти с помощью жадного алгоритма. несколько похожим концептуально является алгоритм Дейкстры, чтобы найти кратчайший путь в графе. фактически в обоих случаях соответствующие «теоремы» почти совпадают с алгоритмами.

ВЗН
источник
Я думаю, что это будет лучшим ответом, если, например, вы включите утверждение свойства cut MST и упомяните, как оно подразумевает правильность целого класса жадных алгоритмов MST.
Сашо Николов
MST вырезать свойства, перечисленные в википедии pg. может быть, вы можете привести другие обобщения, которые там не рассматриваются. Кстати, вспомните, что спрашивающий попросил примеры, служащие «тем, кто находится вне поля теории» (другие приведенные хорошие примеры могут быть слишком
сложными
TeTeABeE(A,B)
1

Найдите последовательность чисел Фибоначчи, которые являются произведением других чисел Фибоначчи. Например, число Фибоначчи 8 находится в последовательности, потому что 8 = 2 * 2 * 2, а 2 - это число Фибоначчи, которое не равно 8. Число 144 Фибоначчи находится в последовательности, потому что 144 = 3 * 3 * 2 * 2 * 2 * 2, а также 2 и 3 являются числами Фибоначчи, которые не равны 144.

Из теоремы Кармайкла следует, что 8 и 144 являются единственными членами этой последовательности.

Боб Лайонс
источник