Чого не може комп'ютер, або труднорешаемие завдання

Машина повинна працювати, людина - думати.

Принцип IBM

Про завдання і алгоритмах

У середовищі математиків відома така притча. У давні часи, коли ніхто й гадки не мав про комп'ютери та їхні можливості, один індійський мудрець зробив велику послугу своєму правителю. Правитель вирішив віддячити йому і запропонував йому самому вибрати нагороду. На що мудрець відповів, що побажав би бачити шахову дошку, на кожній клітині якій були б розкладені зернятка пшона в наступному порядку: на першому - 2, на другому - 2х2 = 4, на третьому - 2х2х2 = 8, на четвертій 24 = 16, і так далі на всіх клітинах.

Спочатку правитель зрадів легкості розплати. Але ось виконати обіцянку не зміг, тому що він і його слуги навряд чи коли-небудь змогли б відрахувати 264 зерен на останню клітину, що відповідає приблизно 18,4 мільярдів мільярдів (!).

Задача, сформульована у цій притчі, відноситься до розряду тих, при рішенні яких найсучасніший комп'ютер безсилий так само, як в давнину слуги правителя. Знаючи продуктивність сучасних ЕОМ, не становить труднощів переконатися в тому, що користувачеві не вистачить всього його життя для відліку зерен, але в даному випадку це навіть не найголовніше. Суть проблеми в тому, що досить незначно змінити вхідні дані, щоб перейти від розв'язуваної задачі до нездійсненним. Кожна людина в залежності від своїх рахункових здібностей може визначити, починаючи з якою клітини (п'ятнадцята чи допустимо, вісімнадцятої) продовжувати відраховувати зерна для нього не має сенсу. Те ж саме можна визначити і для ЕОМ, для якої подібні характеристики написані в технічній документації.

У випадках, коли незначне збільшення вхідних даних задачі веде до зростання кількості дій, що повторюються в степеневий залежності, то фахівці з алгоритмізації можуть сказати, що ми маємо справу з неполіноміальним алгоритмом, тобто кількість операцій зростає в залежності від числа входів за законом, близьким до експоненті ех (е