НГУ

У меня есть несколько вопросов по этим машинам. Просьба специалистам по возможности высказаться.

Первый вопрос: есть известная теорема Агравала-Каяла-Саксены, которая говорит, что множество простых чисел полиномиально вычислимо. Спрашивается, что это означает? Если мы излагаем теорию алгоритмов на основе машин Тьюринга, это означает следующее. На ленту машины выкладывается число , записанное в максимально короткой форме. Такая запись занимает символов. Затем запускается алгоритм, который за шагов, где - длина входа, определяет, является ли простым.

В итоге мы получаем алгоритм, который за шагов определяет простоту числа .

Вопрос 1: если мы излагаем теорию алгоритмов на основе машин Шёнфилда, как мы можем сформулировать эту теорему? Ведь у нас нет ленты, значит, нет понятия "длина входа". Регистры машины Шёнфилда безразмерны и могут содержать в себе любое число.

Конкретно, в позиционной системе счисления. Основание системы роли не играет. Обычно подразумевается двоичная запись числа.


Если мне не изменяет память, .


А никак не можем!!!

Машина Тьюринга - достаточно адекватная модель реальных вычислительных устройств в плане сложности вычислений. Машина Шёнфилда, увы, всего лишь вычисляет за конечное время то, что вычислимо за конечное время на МТ. Для изложения теории сложности она не годится.

_________________
Don't let the sun blast your shadow
Don't let the milk float ride your mind

По-видимому, действительно так. Мы могли бы ввести длину входа аксиоматически: например, если при запуске МШ в некоторых ячейках находятся ненулевые числа , то длиной входа можно было бы считать . Но в этом случае, например, задача распознавания равенства двух чисел x и y станет экспоненциально сложной: если в двух регистрах МШ лежат x и y, то легко показать, что меньше чем за \min(x,y) шагов вопрос об их равенстве точно не решить.

На одноленточной МТ эта задача решается за квадратичное время, а на двухленточной - за линейное.

Тогда у меня вопрос к В.П.: Вы, кажется, по работе располагаетесь поближе к сложности вычислений: понятию "число шагов работы алгоритма" у вас какое точное определение даётся?

эх, а даже я не знал, что есть такая теорема. чему учился столько лет :)

Бывают разные модели вычислений. Как правило в модели формально определяется сложность вычислений, а понятие по смыслу подобное "числу шагов работы алгоритма" есть не всегда. Приведу два примера, когда подобное понятие есть.
1. Ветвящиеся программы (BDD http://en.wikipedia.org/wiki/Binary_decision_diagram ). Это такой ориентированный граф без циклов со степенью исхода 2, каждая внутренняя вершина дерева помечена некоторой переменной. Граф имеет начальную вершину и две конечные 0 и 1. Если переменная равна 0 идём в левого сына, 1 - в правого. Если значение булевой функции 0, то должны попасть в конечную вершину 0. Здесь "числу шагов работы алгоритма" соответствует глубина схемы - число вершин в самом длинном ориентированном пути. Аналогично определятся глубина в разных схемах из функциональных элементах, контактно-вентильных схемах и т.д.
2.Клеточные автоматы http://en.wikipedia.org/wiki/Cellular_automaton
Это такой ориентированный граф, в каждой вершине которого помещена функция, переменными которой служат значения в соседних вершинах. За один такт одновременно пересчитываются значения во всех вершинах. "Число шагов работы алгоритма" - это, конечно, число тактов. Аналогично определяется число шагов алгоритма для разных специализированных конечных автоматов ( игра "жизнь", дискретная генная сеть).

Я, может быть, имел в виду не столько Вашу узкую специальность, сколько дискретную математику в целом. Попробую переформулировать: пусть мы произносим фразу "число компонент связности конечного неориентированного графа может быть определено за полиномиальное число шагов".

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

P.S. Что-то старая гвардия на форум подтянулась! То IVM выплыл из глубины веков, то вот salmin...

Сложность вычислений точно не моя узкая специальность.

Если определено в каком виде задан граф (длина входа), то "сложность вычисления" в крупном масштабе (линейная, полиномиальная, NP и т.д.) понимается однозначно. Так как все "разумные" вычислительные преобразования в данном масштабе имеют вполне определённую сложность.

С другой стороны прибавление единицы на МШ происходит мгновенно, а на МТ на это требуется хотя бы и линейное, но всё же время...

_________________
Don't let the sun blast your shadow
Don't let the milk float ride your mind

С графом в смысле входа картина довольно ясная: если число вершин равно N, он задаётся матрицей NxN из 0 и 1, и длину входа можно по умолчанию считать равной N^2 с точностью до константы.

Но чтобы достичь такого тотального единомыслия, нужны ведь какие-то определения? У меня вопрос, в чём они состоят. Как на практике определяется число шагов алгоритма, хотя бы примерно?

Обычно алгоритм состоит из известных операций: арифметические, полный перебор, сортировка, какие-то задачи класса NP (поиск клики, гамильтонова цикла и т.д.). Для каждой операции верхняя оценка числа операций известна, остаётся правильно оценить параметры операций.

На практике этого, наверное, достаточно. Но странно, что нет общепринятого стандартного определения. Не Моисей же сообщил человечеству эти оценки.

Нет ну я полагал, что в конечном счёте оценки сводятся к вычислениям на Машине Тьюринга. Формальное определение класса NP обращается именно к ней.

Ага, я тоже всегда так полагал. И вроде в книге Пападимитроу написано то же самое. Моисей = Алан Тьюринг

Причём если берём время вычислений с точностью до полинома, то неважно, сколько у МТ лент и т. п. Все достаточно распространённые в литературе конфигурации МТ полиномиально сводятся друг к другу.

P. S. Кстати, есть такая теорема: язык является регулярным (распознаётся конечным автоматом) тогда и только тогда, когда он распознаётся на недетерминированной МТ за линейное время. Вот про это я слышал лишь краем уха, хотелось бы где-нибудь прочитать подробнее.

_________________
Don't let the sun blast your shadow
Don't let the milk float ride your mind

Как то даже обидно за машины...



Эти логарифмы называются логарифмическим весовым критерием для определения сложности вычисления операций на машинах Шенфилда, с произвольным доступом к памяти (RAM), и т.п. Противовес - равномерный весовой критерий, где от размера числа сложность выполнения операции не зависит.

Вот типичные утверждения из "метрической" теории алгоритмов, которой Коба отказалв существовании :

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