align="justify">, якщо , то включаємо в кон'юнкцію . Довільна функція може бути представлена ​​у вигляді
(1.1)
У такому випадку говорять, що представлена ​​в діз'юнктівной нормальній формі (ДНФ), тобто як диз'юнкція кон'юнкцій літералов1) <# "16" src = "doc_zip351.jpg"/>, що обчислює функцію, називається схемної складністю функції в базисі і позначається. Перехід від одного повного кінцевого базису до іншому повного кінцевого базису змінює схемну складність функцій на множник. Так що в асимптотичних оцінках вибір конкретного повного базису неважливий і тому будемо використовувати позначення для схемної складності в кінцевому повному базисі. p> Кожен предикат на безлічі визначає послідовність булевих функцій наступним чином:, де праворуч стоїть характеристична функція предиката.
Визначення 1.5. Предикат належить класу, якщо. p> Теорема 1.2. . p> Якщо МТ працює за поліноміальний час, то і пам'ять, яку вона використовує, обмежена поліномом. Тому весь процес обчислення на вхідному слові довжини можна представити таблицею обчислення розміру, де,. br/>В
Малюнок 1.2: Процес обчислення
Рядок з номером таблиці задає стан МТ після тактів роботи. Символи, записані в таблиці, належать алфавітом. Символ визначає пару (символ, записаний у-й комірці після тактів роботи; стан керуючого пристрою після тактів роботи, якщо головка знаходиться над-й осередком, в іншому випадку другий елемент пари -). Для простоти також вважаємо, що якщо обчислення закінчується при деякому вході за тактів, то рядки c номерами, більшими, повторюють рядок з номером. p> Побудувати схему, яка обчислює значення предиката на словах довжини, можна таким чином. Стан кожної клітини таблиці можна закодувати кінцевим (не залежних від) числом булевих змінних. Є локальні правила узгодження, тобто стан кожної клітини в рядку нижче нульової однозначно визначається станами клітин в попередньому рядку, що лежать безпосередньо над даною (), лівіше даної () і правіше даної (). Кожна змінна, що кодує стан клітини, є функція від змінних, що кодують стану клітин,,. Всі ці функції можуть бути обчислені схемами кінцевого розміру. Об'єднуючи ці схеми, отримаємо схему, яка обчислює всі змінні, що кодують стану клітин таблиці; розмір цієї схеми буде. p> Залишилося помітити, що змінні, що кодують частина клітин нульової рядки, визначаються вхідним словом, а змінні, що кодують інші клітини нульової рядки, є константами. Щоб дізнатися результат обчислення, потрібно визначити символ, записаний в нульовій комірці стрічки в кінці обчислення. Без обмеження спільності можна вважати, що стану клітин таблиці кодуються так, що одна з кодують змінних дорівнює 1 тільки в тому випадку, коли в осередку записана 1. Тоді значення цієї змінної для коду та буде результатом обчи...
