Сложность компьютерных алгоритмов

[vlapay]

Как известно, любая компьютерная программа или остановится, или зациклится за время $T<2^N$, где $N$ - количество бит программы и использованной памяти. У меня вопрос - существуют ли задачи, алгоритмы которых не могут решить за время $T>N^2$, где $N$ - количество бит программы и использованной памяти? Хочу подчеркнуть, что речь идёт именно о наличии строгого математического доказательства для компьютерной программы, то есть числа имеют ограниченную длину, применяются операции компьютерного округления. Нигде на глаза не попадалось подобное доказательство, а вопрос интересный.
Заранее благодарю всех участников.

[Sonic86]

Возможно я не понял вопрос, он мне кажется каким-то тривиальным. Мне кажется, что Вы спрашиваете, существуют ли задачи, которые "не влазят" в конечный комп ($N^2$ тут даже не при чем). Так конечно существуют - любой достаточно длинный экземпляр любой массовой задачи. Например, вычислить $2^{N^2+1}+1$.

Я не угадал?

vlapay в сообщении #1021195 писал(а):

то есть числа имеют ограниченную длину

Это нечто непонятное совсем. Вот дана Вам строка. Как понять, "означает" ли она число или нет?

[vlapay]

Sonic86 в сообщении #1021233 писал(а):

Я не угадал?

Нет.

Цитата:

Вот дана Вам строка. Как понять, "означает" ли она число или нет?

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

[arseniiv]

vlapay в сообщении #1021195 писал(а):

задачи, алгоритмы которых не могут решить

Не понял. Можно переформулировать?

vlapay в сообщении #1021195 писал(а):

Как известно, любая компьютерная программа или остановится, или зациклится за время $T<2^N$, где $N$ - количество бит программы и использованной памяти.

Что значит «зациклится за время»?

[vlapay]

arseniiv в сообщении #1021254 писал(а):

vlapay в сообщении #1021195 писал(а):

задачи, алгоритмы которых не могут решить

Не понял. Можно переформулировать?

Алгоритм, применяемый в программе (сама программа) не может найти решение задачи за время ...

Цитата:

Что значит «зациклится за время»?

Движение программы по замкнутому циклу, если такое случается, может произойти не сразу, а за определённое время.

[Sonic86]

arseniiv в сообщении #1021254 писал(а):

Что значит «зациклится за время»?

Он имеет ввиду ту тривиальную вещь, что комп зациклится максимум спустя $2^N$ тактов. Т.е. число состояний у компа конечно и переход из одного состояния в другое детерминирован. Значит, если прога детерминирована и при ее исполнении комп выполнил $2^N$ тактов, то он зациклился.

vlapay в сообщении #1021249 писал(а):

Вот у нас есть набор гирь с разными весами, натуральными числами. Как найти количество вариантов наборов гирь, дающих один и тот же вес? Существует ли строгое математическое доказательство, что не существует "быстрого алгоритма", могущего выдать число этих наборов гирь?

"быстрого алгоритма" - это алгоритма со скоростью работы $\Omega(f(n))$, т.е. не быстрее, чем $Cf(n)$?
Для каких-то задач есть такое доказательство (помнится, у Верещагина и Шеня написано, что нижние оценки алгоритмов - это трудно). Например, очевидно, что если скорость работы алгоритма не меньше функции длины входных данных. (сумма целых чисел с $n$ разрядами делается не быстрее, чем за $O(n)$, сложение матриц - не быстрее, чем за $O(n^2)$)
Но это все исключительно свойства массовых задач безотносительно к компу. При чем здесь комп?


В общем, Ваша проблема в формулировке. Выразитесь максимально точно.

vlapay в сообщении #1021249 писал(а):

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

Вот здесь нечто странное.
Что такое массовая задача? Массовая задача - это бесконечное семейство задач, параметризованное конечным множеством переменных. Поскольку массовая задача бесконечна, найдется конкретный экземпляр массовой задачи, длина которого не влезет в комп/программу с с ограниченным количеством бит памяти, используемой в вычислениях. И что делать будем?

[Dmitriy40]

vlapay в сообщении #1021195 писал(а):

Как известно, любая компьютерная программа или остановится, или зациклится за время $T<2^N$, где $N$ - количество бит программы и использованной памяти. У меня вопрос - существуют ли задачи, алгоритмы которых не могут решить за время $T>N^2$, где $N$ - количество бит программы и использованной памяти?

Существуют. Для доказательства достаточно привести пример.
Вот он: поставим задачу нахождения периода последовательности чисел разрядности $N-C$ (C - длина программы), каждое следующее число формируется из предыдущего по заданному правилу (реализованному в программе). Программа выполняет $2^{N-C}+1$ шагов вычисления следующего числа, потом запоминает одно вычисленное число, потом снова выполняет шаги преобразования числа до получения равного запомненному. Количество шагов будет равно периоду. Для некоторых правил преобразования числа и некоторых начальных значений период будет не меньше $2^{N-C}-1$, что можно сделать много больше величины и $(N-C)^2$ и $N^2$ выбором достаточно большого $N$. Пример правила преобразования чисел - простой двоичный счётчик.

[Sonic86]

(Оффтоп)

Dmitriy40 в сообщении #1021276 писал(а):

Существуют. Для доказательства достаточно привести пример.

Угу, я ему тоже сначала так сказал.
Тут проблема в том, чтобы понять, что хочет клиент.

[Dmitriy40]

Добавление.
Если расширить задачу до поиска периода заранее неизвестной формулы преобразования числа, то не уверен что её можно решить за количество шагов менее $2^{N-C}$ - тот же самый простейший двоичный счётчик (а для особо наивных - в коде Грея с инвертированными отдельными разрядами - угадывайте! ). Т.е. границу $(N-C)^2$ и $N^2$ превышаем с большим запасом (для достаточно больших N).

[arseniiv]

Sonic86 в сообщении #1021272 писал(а):

Он имеет ввиду ту тривиальную вещь, что комп зациклится максимум спустя $2^N$ тактов. Т.е. число состояний у компа конечно и переход из одного состояния в другое детерминирован. Значит, если прога детерминирована и при ее исполнении комп выполнил $2^N$ тактов, то он зациклился.

А-а-а, т. е. тут прога — это КА, а не машина Тьюринга. Спасибо, да, действительно тривиально.

[vlapay]

Dmitriy40 в сообщении #1021276 писал(а):

Существуют. Для доказательства достаточно привести пример.
Вот он: поставим задачу нахождения периода последовательности чисел разрядности $N-C$ (C - длина программы), каждое следующее число формируется из предыдущего по заданному правилу (реализованному в программе). Программа выполняет $2^{N-C}+1$ шагов вычисления следующего числа, потом запоминает одно вычисленное число, потом снова выполняет шаги преобразования числа до получения равного запомненному. Количество шагов будет равно периоду. Для некоторых правил преобразования числа и некоторых начальных значений период будет не меньше $2^{N-C}-1$, что можно сделать много больше величины и $(N-C)^2$ и $N^2$ выбором достаточно большого $N$. Пример правила преобразования чисел - простой двоичный счётчик.

По моему, этот пример не может считаться доказательством. Доказательство будет тогда, когда будет доказано, что нельзя упростить программу, то есть, что не существует какой-то другой программы, могущей получить тот же результат вычислений за гораздо более короткое время. В этом суть вопроса.

Sonic86 в сообщении #1021272 писал(а):

"быстрого алгоритма" - это алгоритма со скоростью работы $\Omega(f(n))$, т.е. не быстрее, чем $Cf(n)$?
Для каких-то задач есть такое доказательство (помнится, у Верещагина и Шеня написано, что нижние оценки алгоритмов - это трудно). Например, очевидно, что если скорость работы алгоритма не меньше функции длины входных данных. (сумма целых чисел с $n$ разрядами делается не быстрее, чем за $O(n)$, сложение матриц - не быстрее, чем за $O(n^2)$)
Но это все исключительно свойства массовых задач безотносительно к компу. При чем здесь комп?

Вот именно, это направление меня интересует. Может кто-то знает, существует ли хоть один алгоритм, для которого доказано, что "не быстрее, чем за $O(n^2)$"?
Комп универсален и ограничен в ресурсах, и в этом его сила, так как и наш мир ограничен в ресурсах. В его основе лежать минимально необходимые логические операции, а это фундаментальный уровень.

Цитата:

В общем, Ваша проблема в формулировке. Выразитесь максимально точно.

Пытаюсь.

Цитата:

Что такое массовая задача? Массовая задача - это бесконечное семейство задач, параметризованное конечным множеством переменных. Поскольку массовая задача бесконечна, найдется конкретный экземпляр массовой задачи, длина которого не влезет в комп/программу с с ограниченным количеством бит памяти, используемой в вычислениях. И что делать будем?

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

[arseniiv]

vlapay в сообщении #1021291 писал(а):

а в идеале - существует ли универсальный алгоритм-ускоритель, который любые программы с вложенными циклами может "распрямить", получить тот же результат без циклов?

Этот вопрос тоже не очень-то поставлен, но если его как-то понимать, то, например, бывают циклы, тело которых при любом раскладе выполняется конечное число раз, а бывают остальные, но и первые «распрямлять» не обязательно выйдет — какой-нибудь for i in 1..n, если n — аргумент программы.

[Dmitriy40]

vlapay в сообщении #1021291 писал(а):

Dmitriy40 в сообщении #1021276 писал(а):

Существуют. Для доказательства достаточно привести пример.

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

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

[vlapay]

arseniiv в сообщении #1021307 писал(а):

vlapay в сообщении #1021291 писал(а):

а в идеале - существует ли универсальный алгоритм-ускоритель, который любые программы с вложенными циклами может "распрямить", получить тот же результат без циклов?

Этот вопрос тоже не очень-то поставлен, но если его как-то понимать, то, например, бывают циклы, тело которых при любом раскладе выполняется конечное число раз, а бывают остальные, но и первые «распрямлять» не обязательно выйдет — какой-нибудь for i in 1..n, если n — аргумент программы.

Уточню - можно ли получить ограниченный объём вычислений, не более $N^2$, с помощью универсального алгоритма-ускорителя?

Dmitriy40 в сообщении #1021327 писал(а):

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

Это только так кажется. По-видимому, таких доказательств не существует в природе.
Вопрос об универсальном алгоритме-ускорителе интересен и фундаментален. Как известно, программа может проверять правильность математических выкладок. Формулируем теорему, вводим набор математических понятий, делаем программу, хаотически подставляющие все эти символы в "доказательство" и программу, проверяющую результат этого хаоса (вложенные циклы в переборной задаче). Если есть универсальный алгоритм, то мы можем быстро получить доказательство любой теоремы (решение любой задачи), если такое вообще существует в природе.
Математики как рабочий класс вообще не нужны. Достаточно доказать, что такого универсального алгоритма не существует в природе и требовать повышения зарплаты.

[Sonic86]

vlapay в сообщении #1021291 писал(а):

Вот именно, это направление меня интересует. Может кто-то знает, существует ли хоть один алгоритм, для которого доказано, что "не быстрее, чем за $O(n^2)$"?

Так я же Вам объясняю: пусть есть задача, у которой длина входа $=d(n)$, тогда время работы алгоритма $=\Omega(d(n))$ (за исключением каких-нибудь дурацких задач типа "вернуть 1-й элемент из массива длины $n$").
Пример: вычислить сумму квадратных матриц $n\times n$. Это нельзя сделать быстрее, чем за $O(n^2)$ просто потому, что в матрице $n^2$ разных элементов и они независимы друг от друга; просто потому, чтобы написать ответ потребуется $O(n^2)$ элементов.

vlapay в сообщении #1021291 писал(а):

а в идеале - существует ли универсальный алгоритм-ускоритель

Смотря, что под этим понимается. Для вычисления конечной функции есть единственный универсальный вариант - полное упорядочивание входных данных (лексикографическое )и табулирование функции, оно работает за $O(D\ln n)$, где $D$ - максимальная длина значения функции. (тоже, давно известно, что поиск в массиве с произвольным свойствами невозможно выполнить быстрее чем за $O(\ln n)$, где $n$ - длина массива, т.е. скорость поиска всегда $\Omega(\ln n)$).

vlapay в сообщении #1021291 писал(а):

который любые программы с вложенными циклами может "распрямить", получить тот же результат без циклов?

Очевидно, что цикл "распрямить" нельзя. Просто потому, что длина входной задачи не ограничена. Например, дано $n$ элементов, надо найти их сумму.

vlapay в сообщении #1021429 писал(а):

Уточню - можно ли получить ограниченный объём вычислений, не более $N^2$, с помощью универсального алгоритма-ускорителя?

Похоже, что уже бред пошел
Еще раз говорю: Вы не сформулировали вопрос нормально. Что такое "универсальный алгоритм-ускоритель"? $N$ - это у Вас что? Откуда берется $N^2$?
Пока Вы будете изливать мутный поток сознания, ни разу не обработанный, помочь Вам никто не сможет.

vlapay в сообщении #1021429 писал(а):

Вопрос об универсальном алгоритме-ускорителе интересен и фундаментален.

Вопрос пока отсутствует.

vlapay в сообщении #1021429 писал(а):

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

Бред, доказательство теоремы - $NP$-полная задача.