Существует большая разница между задачами непростыми и задачами сложными. Задача может не иметь эффективных решений в самых худших случаях, но может оставаться легко решаемой для большинства случаев, или для случаев, возникающих на практике. Поэтому общепринятые определения сложности задач могут оказаться относительно бессмысленными в терминах реальной сложности, так как две задачи могут быть NP-полными, но одна при этом в большинстве случаев может решаться быстро, а другая нет. Как следствие, важную роль в теории сложности играет понятие «сложности в среднем» (здесь под «средним» понимается математическое ожидание времени решения).
Чтобы проиллюстрировать центральную роль этого понятия, можно вообразить пять различных возможных миров (возможных — потому что еще не доказано, что они нереальны, и наш может оказаться любым из них) и посмотреть как условия в них будут влиять на информатику и жизнь вообще.
В частности, для демонстрации с точки зрения человека, будем использовать печальную историю Профессора Гроуса, того самого преподавателя математики, который задал классу задачку — сосчитать сумму чисел от 1 до 100. Всем известно, что на его беду в классе оказался маленький Гаусс, который быстро заметил закономерности арифметической прогрессии и почти моментально посчитал эту сумму. Но мало кто знает, что после этого Профессором овладела навязчивая идея отомстить Гауссу и унизить его перед всем классом, придумывая задачи, которые Гаусс не мог решить. Это привело Профессора в сумасшедший дом (не самый приятный конец, особенно в 19 веке), а у Гаусса развило интерес к теоретико-числовым алгоритмам. Попробуем представить что было бы в различных мирах, которые будем рассматривать.
Алгоритмика
Алгоритмика — это мир, в котором P = NP. В этом мире Профессору везло бы еще меньше, чем в реальности. Так как Профессору нужно поставить в тупик Гаусса задачей, на которую он (Профессор) затем должен сам показать классу верный ответ, он ограничен в выборе задач теми, которые имеют легко проверяемое решение (то есть задачи из NP). Гаусс может использовать метод проверки, чтобы автоматически решить эту задачу.
Метод автоматического получения алгоритма решения проблем из алгоритма проверки верного решения произведет революцию в информатике того мира. Задачи, которые казались неподдающимися, окажутся тривиальными. Почти все задачи оптимизации будут простыми и автоматическими. Например, в проектировании СБИС больше не будут использоваться эвристики, вместо этого будет генерироваться оптимальная проводка, если задан критерий оптимальности. Языки программирования больше не будут содержать инструкции, описывающие как выполнять вычисления. Вместо этого они только будут описывать свойства, которыми должны обладать выходные данные по отношению к входным данным. Компилятор будет самостоятельно переводить язык спецификаций в алгоритм решения.
Менее очевидно, что P=NP сделает тривиальными многие аспекты программ искусственного интеллекта. Можно будет использовать обучающиеся системы, основывающиеся на принципе «бритвы Оккама», чтобы автоматически обучать компьютер выполнять действия, которые могут делать люди. Достаточно будет обеспечить обучающую выборку входных данных и выходных данных, произведенных человеком-экспертом, и компьютер выведет простейший алгоритм, которые будет выдавать те же ответы, что и эксперт. Так, компьютер можно будет научить распознавать и разбирать предложения на естественном языке, нужно только обеспечить достаточное количество примеров верных и неверных предложений (здесь предполагается, что существует некий простой алгоритм, который люди используют для разбора естественных языков).
С другой стороны, в Алгоритмике не будет возможности различить людей и компьютеры с информационной точки зрения. Упомянутые обучающиеся алгоритмы смогут легко научиться имитировать поведение других машин и даже людей. Любой код, который может быть разработан, так же легко может быть взломан. Мало пользы будет от попыток скрыть алгоритм, на котором основан код, так как такой же алгоритм можно будет легко получить, имея небольшое количество пар шифротекст — плейнтекст. Не будет возможности обеспечить доступ к информации нескольких людям, не делая ее таким образом доступной для всех. Поэтому любые способы идентификации должны будут быть основаны на физических измерениях. И безопасность идентификации будет базироваться на неизменности физических параметров и устойчивости к внешним воздействиям каналов передачи данных от измерителя к идентификационному устройству.
Эвристика
Эвристика — это мир, в котором задачи из NP не имеют эффективных решений в худшем случае, но легко решаемы в среднем (для некоторого распределения вероятностей на множестве входов).
Эвристика, в некотором роде, парадоксальный мир. Здесь существуют сложные экземпляры задач из NP, но найти такой сложный экземпляр — сама по себе сложно решаемая задача. В этом мире Профессор будет иметь возможность найти задачи, которые окажутся не по зубам Гауссу. Но ему придется потратить неделю на поиск задачи, которую Гаусс не сможет решить в течение дня, и год, чтобы найти задачу, на которую Гаусс потратит месяц (в данном случае предполагается, что Гаусс имеет некоторое полиномиальное преимущество над профессором, ведь Гаусс, в конце концов, гений). Скорее всего, жизнь не настолько сурова, чтобы предоставлять нам сложные задачи, лишь бы жизнь малиной не казалась. Поэтому для практических целей этот мир почти неотличим от Алгоритмики.
Или все же отличим? В Эвристике среднее время решения задачи из NP зависит от среднего времени «обдумывания» этой задачи. Это несколько усложняет ситуацию. Допустим, в среднем, вычисление решения задачи в два раза дольше придумывания решения. Если мы тратим время T на обдумывание задачи №1, то мы потратим 2T единиц времени на вычисление решения. Решение этой задачи влияет на решение задачи №2, т.е. на обдумывание решения задачи №2 мы потратили 3Т единиц времени. Поэтому на решение задачи №2 будет потрачено 6Т единиц времени. Что приводит к задаче №3, на обдумывание которой мы уже потратили 10Т единиц времени, следовательно 20Т будет потрачено на решение. Так как эта рекурсия экспоненциально растет, уже через несколько шагов мы пересечем границу между «осуществимым» и «нереальным».
В случае дизайна СБИС здесь уже не обязательно будут эффективные решения, так как в данном случае нас мало интересует большинство возможных подходящих под спецификации схем, а важны минимальные варианты, удовлетворяющие спецификациям. Такие схемы могут не иметь хорошего распределения, и, так как, скорее всего, понадобится экспоненциальное время для их поиска, нет никаких гарантий, что они не являются теми самыми «худшими случаями», на которых плохо работают алгоритмы в Эвристике.
В криптографии и сетевой безопасности не будет принципиальных различий с Алгоритмикой. Мало толку будет, если добросовестные пользователи будут тратить много времени на поиск экземпляра задачи, которая могла бы однозначно их идентифицировать, когда злоумышленник может решить этот экземпляр за сравнимое количество времени (предполагается, что злоумышленник, который хочет взломать систему, использует значительно больше ресурсов, чем добросовестный пользователь).
Пессиландия
Пессиландия — это худший из возможных случаев — в ней есть задачи, решаемые сложно даже в среднем, но нет односторонних функций. Под отсутствием односторонних функций понимается следующее: для любой задачи, которую легко вычислить, также легко найти решение обратной задачи, в том смысле, что для почти всех значений x, если дано F(x), то можно найти некоторый x', такой, что F(x') = F(x), причем примерно за то же время, что тратится на вычисление F(x).
В Пессиландии Профессор смог бы задать Гауссу задачки, которые даже молодой гений не смог бы решить. Но и сам Профессор не смог бы продемонстрировать решение, так что унижение Гаусса было бы неполным.
В этом мире во многих областях задачи не имели бы легких решений. Прогресс был бы как и в нашем мире: медленно продвигался бы за счет более глубокого понимания мира и за счет использования не совсем удовлетворительных эвристик. Общие методы решения задач не работали бы в большинстве областей. Однако несколько полезных алгоритмов были бы возможны, базируясь на отсутствии односторонних функций. Например, метод сжатия данных, в котором, зная распределение входных данных, в пределе можно было бы их сжимать до ожидаемой длины в соответствии с энтропией распределения.
В этом мире не будет возможности использовать сложные задачи в криптографии. Задача, на которую никто не знает ответ, не может быть использована для отличия добросовестного пользователя от злоумышленника.
Миникрипт
В Миникрипте есть односторонние функции, но невозможна криптография с открытым ключом. Здесь мы понимаем под криптографией с открытым ключом задачу засекреченного общения через публичные каналы связи, хотя, строго говоря, криптография с открытым ключом — лишь один из способов решения этой задачи.
Односторонние функции могут использоваться для генерации сложных, но решенных задач, а именно: генератор будет выбирать х, вычислять y = F(x) и ставить задачу поиска «найти такой x', что F(x') = y». Таким образом, в Миникрипте Профессор, наконец, сможет одержать верх над Гауссом перед всем классом.
В сети участники смогут идентифицировать себя перед другими пользователями, а также удостоверять сообщения с использованием цифровой электронной подписи. Будет возможно доказывать факты о секрете, не открывая другую секретную информацию, содержащуюся в нем. Если небольшое количество информации заранее передано между участниками, то можно установить надежный секретный код между двумя участниками сети, который позволит им общаться в закрытом порядке, используя открытые каналы связи. Однако, невозможно будет провести тайное голосование через открытые каналы, или обеспечить безопасные переговоры, не пересылая заранее некоторую информацию через защищенные каналы. Не будет возможности создать анонимные цифровые деньги.
Криптомания
В Криптомании криптография с открытым ключом существует. В Криптомании Гаусс будет унижен еще больше; Профессор и его ученик-любимчик смогут совместно выбрать задачу, на которую они оба будут знать ответ, а Гаусс ее решить не сможет. Более того, в этом мире Профессор сможет сделать так, что все в классе будут знать как решить заданную задачу, кроме Гаусса.
Из существования протоколов с открытым ключом следует существование односторонних функций, поэтому в этом мире все еще существуют псевдо-случайность, цифровые подписи, идентицикация, протоколы с нулевым знанием и прочее. Также, если засекреченный обмен производится с помощью односторонних функций с секретом (а все известные протоколы явно или косвенно используют именно такие функции), можно решить любые вообразимые криптографические задачи. В отличие от других миров, где создание конфиденциальности — это технологическая задача, технологии в Криптомании наоборот будут ограничивать возможности пользователей к уменьшению конфиденциальности. Большинство решений по тому, сколько конфиденциальности позволено гражданам, будут приниматься в результате политических и социальных процессов, а не из-за технических возможностей.
Этот мир больше всего похож на наш с вами., по крайней мере до тех пор, пока считается, что известные протоколы с открытым ключом надежны.
R. Impagliazzo, "A personal view of average-case complexity," sct, pp.134, 10th Annual Structure in Complexity Theory Conference (SCT'95), 1995
Изображение позаимствовано с сайта XKCD.
