Конструктивно эффективные алгоритмы без эффективной корректности и доказательства эффективности

17

Я ищу естественные примеры эффективных алгоритмов (т.е. в полиномиальном времени)

  1. их правильность и эффективность могут быть доказаны конструктивно (например, в прA или ), ноЧАСA
  2. не известно никаких доказательств, использующих только эффективные концепции (то есть мы не знаем, как доказать их правильность и эффективность в или ).S 1 2TВ0S21

Я могу сделать искусственные примеры самостоятельно. Однако я хочу интересные естественные примеры, то есть алгоритмы, которые изучаются сами по себе, а не созданы только для того, чтобы ответить на этот тип вопросов.

Кава
источник
1
Возможно, что-то из теории автоматов, где алгоритм прост, но чтобы показать, что он работает, нужно рассмотреть все подмножества того или иного?
Андрей Бауэр
2
Как насчет проверки простоты за полиномиальное время? Это доказательство, вероятно, будет достаточно сложным, чтобы его было трудно вставить в ? S21
Андрей Бауэр
4
@Neel, на самом деле тезис Эмиля « Принцип слабой ямы и рандомизированные вычисления » о формализации вероятностных алгоритмов. Основной аксиомой, необходимой для формализации некоторых из них, является приблизительный подсчет, который не является частью или S 1 2 . Я думаю, что было бы проще придерживаться детерминированного случая сложного времени с T V 0 и S 1 2 . TВ0S21TВ0S21
Каве
1
ps: было бы более интересно, если бы мы могли доказать, что правильность / эффективность алгоритмов не доказуема в этих теориях или, по крайней мере, эквивалентна утверждениям, которые, как полагают, недоказуемы в них. Однако просить об этом, вероятно, слишком много с тем, что мы знаем в настоящее время.
Каве
4
@Neel, большая часть релевантной вероятности может быть получена в системах первого порядка, так как вам действительно не нужно знать точную вероятность события, вам обычно нужно только сравнить эту вероятность с определенными рациональными числами.
Франсуа Г. Дорайс

Ответы:

14

Это та же идея, что и в ответе Андрея, но с более подробной информацией.

Крайчек и Пудлак [ LNCS 960, 1995, с. 210-220 ] показали, что если является Σ b 1 -свойством, определяющим простые числа в стандартной модели, и S 1 2¬ P ( x ) ( y 1 , y 2 ) ( 1 < y 1 , y 2 < x x = y 1 y 2 )п(Икс)Σ1б

S21¬п(Икс)(Y1,Y2)(1<Y1,Y2<ИксИксзнак равноY1Y2)
тогда есть полиномиальный алгоритм факторинга времени. Это дает множество примеров, поскольку любой алгоритм NP для тестирования простоты в основном дает такую формулу . В частности, критерий простоты AKS дает такую ​​формулу (при соответствующей переработке на языке S 1 2 ). В статье Крайчека и Пудлака приводятся дополнительные примеры такого рода, связанные с криптографией, но он предшествует AKS и связанным с ним достижениям на несколько лет.Σ1бS21
Франсуа Г. Дорайс
источник
10

TС0ВTС0

TВ0ВTС0TС0

(aN)

п(aп)знак равно1aп

S21

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

Эмиль Йержабек поддерживает Монику
источник
9

Тест на примитивность AKS кажется хорошим кандидатом, если верить Википедии.

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

Андрей Бауэр
источник
2
S21
2
S21S21
2
Крайчек и Пудлак опубликовали замечательную статью, в которой приводится еще несколько примеров: karlin.mff.cuni.cz/~krajicek/j-crypto.ps
Франсуа Г. Дорайс,
2
@ Франсуа, почему бы не опубликовать ответ? :)
Kaveh
8
Итак, я получаю наибольшее количество голосов за раннее счастливое предположение, в то время как другие на самом деле знают, что происходит. Математика так же, как MTV.
Андрей Бауэр