е полягати в тому, що необхідні для цього обчислення ресурси занадто великі. Тому нас цікавить не стільки існування алгоритму для вирішення завдання, скільки існування ефективного алгоритму. p> Формалізувати це поняття непросто. Прийнятий зараз спосіб полягає в тому, що виділяються класи тих функцій або предикатів, обчислення яких можливе за задаються обмеженнях на споживані ресурси.Прінадлежность функції того чи іншого сложностному класу служить зручною характеристикою можливостей її ефективного обчислення, не пов'язаної з конкретними реалізаціями алгоритмів.
Найбільш важливі класи виходять, якщо накладати обмеження на зростання часу роботи та/або використовуваної пам'яті залежно від довжини вхідного слова. А найбільш важлива відмінність між ефективними і неефективними обчисленнями задається функціями полиномиального зростання. Функція - полиномиального зростання, якщо для деякої константи при досить великих виконується нерівність. У цьому випадку будемо використовувати позначення. p> Визначення 1.3. Предикат на безлічі належить класу (і називається полиномиально вичіслімих), якщо його характеристична функція вичіслімих на машині Тьюринга, для якої. p> Визначення 1.4. Предикат на безлічі належить класу, якщо його характеристична функція вичіслімих на машині Тьюринга, для якої. p> За аналогією з предикатами можна визначити і функції, вичіслімих за поліноміальний час, і функції, вичіслімих на поліноміальної пам'яті. Для класів таких функцій також використовуються позначення і, так що точний зміст цих позначень потрібно відновлювати з контексту. br/>
Тема 1.3 Схеми
Схема (булева) - це спосіб обчислити функцію . Крім вихідних змінних , для яких обчислюється значення , схема використовує деяку кількість допоміжних змінних і деякий набір (базис) булевих (тобто приймаючих значення 0 або 1) функцій . Схема в базисі визначається послідовністю присвоювань . Кожне присвоювання має вигляд , де , а змінна < span align = "justify"> ( ) - це або одна з вихідних змінних ( ), або допоміжна змінна з меншим номером ( ). Таким чином, для кожного набору значень вихідних змінних послідовне виконання присвоювань, що входять у схему, однозначно визначає значення всіх допоміжних змінних. Результатом обчислення вважаються значення останніх змінних .
Схема обчислює функцію , якщо для будь-яких...
