Ограничения для вычислений: ученый-компьютерщик объясняет, почему даже в эпоху ИИ некоторые задачи слишком сложны.

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

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

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

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

Воображаемая вычислительная машина

Современное понятие алгоритма , известного как машина Тьюринга, было сформулировано в 1936 году британским математиком Аланом Тьюрингом . Это воображаемое устройство, имитирующее выполнение арифметических вычислений карандашом на бумаге. Машина Тьюринга — это шаблон, на котором основаны все современные компьютеры.

Чтобы приспособиться к вычислениям, для которых потребовалось бы больше бумаги, если бы они выполнялись вручную, запас воображаемой бумаги в машине Тьюринга предполагается неограниченным. Это эквивалентно воображаемой бесконечной ленте или «ленте» квадратов, каждый из которых либо пуст, либо содержит один символ.

Машина управляется конечным набором правил и запускается с начальной последовательности символов на ленте. Операции, которые может выполнять машина, — это перемещение на соседнюю клетку, стирание символа и написание символа на пустой клетке. Машина вычисляет, выполняя последовательность этих операций. Когда машина завершает работу или «останавливается», символы, оставшиеся на ленте, являются выводом или результатом.

Вычисления часто связаны с решениями, на которые можно ответить «да» или «нет». По аналогии медицинский тест (тип задачи) проверяет, имеет ли образец пациента (экземпляр задачи) определенный индикатор заболевания (да или нет ответа). Экземпляр, представленный в машине Тьюринга в цифровом виде, представляет собой исходную последовательность символов.

Проблема считается «решаемой», если можно спроектировать машину Тьюринга, которая останавливается для каждого экземпляра, будь то положительный или отрицательный, и правильно определяет, какой ответ дает экземпляр.

Не каждую проблему можно решить

Многие проблемы решаются с помощью машины Тьюринга и, следовательно, могут быть решены на компьютере, а многие другие — нет. Например, проблема домино, разновидность задачи о мозаике, сформулированная американским математиком китайского происхождения Хао Ваном в 1961 году, неразрешима.

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

Ряд решаемых проблем можно решить с помощью алгоритмов, которые останавливаются за разумное время. Эти « алгоритмы с полиномиальным временем » являются эффективными алгоритмами , что означает практичность использования компьютеров для их решения.

Известно, что тысячи других решаемых задач не имеют алгоритмов с полиномиальным временем, несмотря на продолжающиеся интенсивные усилия по поиску таких алгоритмов. К ним относится задача коммивояжера.

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

Эти проблемы, называемые NP-complete , были независимо сформулированы и продемонстрированы в начале 1970-х годов двумя учеными-компьютерщиками , американским канадцем Стивеном Куком и американцем украинского происхождения Леонидом Левиным . Кук, чья работа была первой, был удостоен за эту работу высшей премии Тьюринга 1982 года в компьютерных науках.

Стоимость знания

Самые известные алгоритмы для NP-полных задач, по сути, ищут решение из всех возможных ответов. Задача коммивояжера на графе из нескольких сотен точек потребовала бы лет для решения на суперкомпьютере. Такие алгоритмы неэффективны, то есть в них нет математических сокращений.

Практические алгоритмы, которые решают эти проблемы в реальном мире, могут предложить только приближения, хотя приближения улучшаются. Существуют ли эффективные алгоритмы с полиномиальным временем, которые могут решать NP-полные задачи , входит в число открытых проблем семи тысячелетий, опубликованных Математическим институтом Клэя на рубеже 21 века, каждая из которых получила приз в размере 1 миллиона долларов США.

Помимо Тьюринга

Может ли существовать новая форма вычислений за рамками Тьюринга? В 1982 году американский физик Ричард Фейнман , лауреат Нобелевской премии, выдвинул идею вычислений на основе квантовой механики .

В 1995 году Питер Шор, американский прикладной математик, представил квантовый алгоритм для факторизации целых чисел за полиномиальное время . Математики считают, что это неразрешимо с помощью полиномиальных алгоритмов в рамках Тьюринга. Факторизация целого числа означает нахождение меньшего целого числа, большего 1, которое может разделить целое число. Например, целое число 688 826 081 делится на меньшее целое число 25 253, потому что 688 826 081 = 25 253 x 27 277.

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

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

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