Ненормальность такой ситуации усугубится, если учесть, что теоретики рассматривают только конечные дискретные задачи (задачи либо на поиск оптимума, либо распознавания [да-нет]), любая из которых (теоретически) может быть решена хотя бы (за неимением лучшего) простым перебором. Но от этого не легче, если вспомнить легенду об изобретателе шахмат, который попросил в награду за первую клеточку шахматной доски одно зернышко, за вторую два… за 64-ю клеточку – 2 в 64-ой степени зернышек. Что превышает зерновые ресурсы Земного шара.
Одна из книг по сложности вычислений начиналась с цитаты из украинского философа Георгия Сковороды:' Спасибо тебе Господи, что ты создал все нужное нетрудным, а все трудное – ненужным.' Но кажется, что здесь более точной будет другая мысль из Сковороды, а именно, эпитафия на его могиле: «Мир ловил меня, но не поймал»… И еще одна мысль более конкретная мысль уже от современных математиков: «Сложность становится проблемой века».
Из-за огромного количества несущественных особенностей различных способов (методов, парадигм) вычисления признаки, которые следовало бы учитывать при определении сложности вычислений слишком многочисленны и противоречивы. Но в конечном счете большинство сходится к тому, что все можно свести к времени (числу элементарных шагов) вычисления и объему памяти. Более того, многие так и видят при этом в качестве наилучших моделей – машины Тьюринга.
Проблему быстро свели к двум словам и их сочетанию.
Эти слова
Возьмем большой мешок камней и решим задачу поиска самого большого камня. Будем вынимать поочередно камни, сравнивая с самым большим на данный момент. Исчерпав мешок мы оставим в руках самый большой камень. Если число камней мы увеличим в 2 раза, то сложность решения задачи тоже увеличится (примерно) в два раза. Если возьмем мешок с 'n' то и трудность решения будет пропорциональна 'n'. Говорят, что такую задачу можно решить за полиномиальное время. Если вы решаете задачу нахождения самого большого ребра в полном нагруженном графе, то это тоже задача полиномиальной сложности, исходя из формулы для полного графа, увеличивающая сложность с ростом числа вершин по закону роста числа ребер, пропорциональному «n квадрат».
Однако, есть задачки (для тех же графов), для которых не найдено простых (полиномиальных) решений. Вторым из классических примеров таких задач (первый оставим для финала) служит задача о коммивояжере: Каков минимальный цикл в нагруженном графе, что при обходе его в каждую вершину заходим однажды. Для этой задачи есть только «трудные решения», сложность которых растет по экспоненте (как число зернышек на шахматной доске).
Но проверить решение такой задачи можно за полиномиальное время. Вся сложность в том, чтобы знать «траекторию решения». А вот снять проблему выбора правильной траектории позволяет недетерминированная машина Тьюринга, которую можно представить как сколь угодно большое число (обычных детерминированных) машин, каждая из которых делает попытку добраться до решения задачи по одной из возможных траекторий. У кого из читателей фантазия при этом отказывает, могут просто представить себе бога (говорят – «оракула»), который подсказывает правильный путь, чтобы не гонять кучу машин неведомыми тропами. Конечный эффект тот же.
Таким образом, множество труднорешаемых задач (
Интересно, говорят этой формулой математики, совпадают ли множество задач, решаемых за полиномиальное время и множество
Как бы там ни было, а задачи, для которых простые (полиномиальные) решения пока не найдены, существуют. И чем дальше, тем больше математики упорствуют в этой (недоказанной) уверенности. Более того, они коллекционируют типовые труднорешаемые задачи, которых уже набралось не менее тысячи. Более того, утверждают, что одни труднорешаемые задачи сводятся к другим труднорешаемым задачам. Поэтому даже используется для таких задач термин '
ПОСЛЕСЛОВИЕ
Самой первой
Но в середине семидесятых годов были опубликованы так называемые '
Мало радости признаваться в собственной бестолковости и некомпетентности, но проблема трудно решаемых задач для меня существует в несколько извращенном виде.
