Что компьютеру сделать легко, а что почти невозможно? Эти вопросы лежат в основе вопроса вычислительной сложности. Представляем вам карту этого ландшафта.
Различные классы сложности сортируют задачи в иерархическом виде. Один класс может содержать все задачи другого, плюс задачи, требующие дополнительных вычислительных ресурсов.
Какова фундаментальная сложность задачи? Такова постановка базовой задачи специалистов по информатике, пытающихся рассортировать задачи по т.н. классам сложности. Это группы, содержащие все вычислительные задачи, требующие не более фиксированного количества вычислительных ресурсов – таких, как время или память. Возьмём простой пример с большим числом типа 123 456 789 001. Можно задать вопрос: является ли оно простым числом – таким, которое делится только на 1 и себя? Специалисты по информатике могут ответить на него при помощи быстрых алгоритмов – таких, что не начинают тормозить на произвольно больших числах. В нашем случае окажется, что это число не является простым. Затем мы можем задать вопрос: каковы его простые множители? А вот для ответа на него быстрого алгоритма не существует – только если использовать квантовый компьютер. Поэтому специалисты по информатике считают, что две этих задачи относятся к разным классам сложности.
Читать полностью »
