Неконструктивная сложность алгоритма

[Bogka]

Допустим, лучший известный алгоритм решения некоторой задачи имеет квадратичную сложность. Но доказано, что эту задачу можно решить линейным алгоритмом, но его никто не знает. Такие ситуации есть? Если докажут, что P=NP, то они точно появятся.

[fflatx]

Bogka в сообщении #1641408 писал(а):

Такие ситуации есть?

Когда проводят анализ алгоритма, то по-хорошему, где-то рядом рассматривают вопрос "почему нельзя быстрее". Если же всё-таки "можно быстрее", то это выяснится тут же, в процессе этого же анализа. А значит, сразу будет ясно, где чего подкрутить.

В ситуации, о которой Вы говорите... Вы как себе это представляете?
Вот у Вас есть алгоритм и он классный. А я прихожу и говорю: Я точно знаю, что можно быстрее. Но я не знаю, как. А если я не знаю, как, то с чего я решил, что можно быстрее? Ну, я доказал математически. А что я доказал-то? Что я анализировал? А я сам не знаю, что я анализировал.
Так что ли? Странно как-то.

А вот если я анализировал существующий алгоритм и увидел, что "можно быстрее", то есть я увидел, где этот алгоритм "не дотягивает", увидел "слабые места", то понятно, что эти "слабые места" и нужно пытаться исправить.

[dgwuqtj]

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

[Bogka]

dgwuqtj
Если в них какая-то процедура, успешно работающая всегда, если выполняется гипотеза, это конструктивно и для практики достаточно. Там действительно доказано неконструкивно?

[dgwuqtj]

А при чём тут практика? Речь идёт про теоретические результаты об абстрактных алгоритмах на абстрактных машинах (скажем, словарных RAM). У самых быстрых алгоритмов умножения матриц, к примеру, такие скрытые константы, что их никто не имплементировал. На практике же часто хватает каких-нибудь приближённых алгоритмов, например, проверку на простоту можно брать вероятностную или недоказанную.

-- 04.06.2024, 21:34 --

Ну и использование теоретико-числовых гипотез - это всё-таки конструктивные доказательства, просто условные. А итоговую сложность не знают, пока не докажут гипотезу или не обоснуют сложность по-другому.

[Bogka]

Пишут, что важная проблема есть или нет линейный алгоритм умножения матриц. Если неконструктивно докажут, что он есть, это будет сильная мотивация его искать. Как и если неконструктивно докажут P=NP, будет мотивация искать полиномиальные алгоритмы традиционно считаемых экспоненциальными задач.

[dgwuqtj]

Ну вот окажется, что есть алгоритм умножения матриц $n \times n$ над полем $\mathbb F_2$ за $10^{100} n^2$ элементарных операций. И докажут, что быстрее асимптотически нельзя. И что?

-- 04.06.2024, 21:51 --

Между $P = NP$ и поиском быстрых алгоритмов для задач из класса $P$ всё-таки большая разница.

[Bogka]

dgwuqtj
А если докажут, что константа 10, то много людей бросятся его искать, и специалисты и нет, в том числе применяя ИИ и создавая новые ИИ под эту задачу. В Дипмайнде улучшили сортировку 5 чисел и умножение матриц 4х4 или около того с помощью ИИ. С учетом того, что к этому рекурсивно приходят алгоритмы на больших размерах, улучшились и они.

[dgwuqtj]

Это, конечно, хорошо было бы.

[svv]

Да, коэффициенты.
Вот тут (Хабр) пишут, что недавно китайцы предложили алгоритм умножения матриц со сложностью $O(n^{2.371866})$, побив прежний рекорд $O(n^{2.3728596})$. Допустим, это им удалось ценой увеличения коэффициента всего в $2$ раза. При каких $n$ уменьшение показателя степени перевесит увеличение коэффициента, и мы таки получим выигрыш в скорости? WolframAlpha говорит, что при $n>9.31102\cdot 10^{302}.$
Если раньше подобные новости и производили на меня какое-то впечатление, то после этого расчёта — точно нет.

[vpb]

(Оффтоп)

Тут и без Вольфрама ясно. Улучшение показателя примерно $0,001$, коэффициент предполагаем увеличивающимся в 2 раза, значит размер, с которого старый алгоритм уступает новому, примерно $2^{1000}\approx 10^{300}$ , ибо $2^{10}\approx 10^3$.

[mihaild]

Bogka в сообщении #1641425 писал(а):

Как и если неконструктивно докажут P=NP

Есть алгоритм Левина, находящий выполняющий набор для выполнимых SAT-формул, и, если P=NP, делающий это за полиномиальное время.

[Bogka]

mihaild
Он как бы полностью выполнимость не решает? Что он делает если формула невыполнима?

[Евгений Машеров]

Мне кажется, что если доказать отсутствие алгоритма меньшей сложности можно даже без предъявления алгоритма, то наличие "быстрого алгоритма" предполагает явное описание алгоритма. Без этого можно только высказывать гипотезу о его существовании. Если говорить о проблеме P=NP, то её решение может состоять лишь в предъявлении полиномиального алгоритма для одной из NP-полных задач. Что вроде как можно трактовать "доказано существование полиномиального алгоритма для всех прочих NP-полных задач, но его никто не знает". Однако в этом классе задач есть алгоритмы сведения одних задач этого класса к другим, то есть полиномиальный алгоритм существует и предъявлен (но может оказаться для конкретной задачи непрактичным).
И касательно непрактичности - общался я некогда с человеком, пытавшимся реализовать в библиотеке программ алгоритм Шенхаге-Штрассена. Проблема там, как я понял с его слов, была связана не столько с большой константой, сколько с тем, что число операций типа сложения резко выросло, и в результате появилась численная неустойчивость.

(Оффтоп)

А ещё в наивные студенческие годы пытался я придумать алгоритм умножения матриц со сложностью $O(n^2\ln n)$, развернув матрицы-сомножители в вектора и вставив нолики между фрагментами, соответствовавшими строкам и столбцам, соответственно...

[mihaild]

Bogka в сообщении #1641459 писал(а):

Он как бы полностью выполнимость не решает? Что он делает если формула невыполнима?

Зависает.