шини - стан вихідний стрічки в кінці роботи. p> Якщо цікавитися складністю алгоритмів з точністю до полиномиально обмеженого множника, багатострічкові машини нічого не додають в порівнянні з описаними вище машинами з єдиною стрічкою.
Доведіть, що двухленточние машину Тьюринга, працюючу за час на входах довжини, можна моделювати на машині з єдиною стрічкою за час.
Доведіть, що трехленточную машину Тьюринга, працюючу за час на входах довжини, можна моделювати на двухленточние за час.
Нехай - машина Тюрінга з єдиною стрічкою, яка копіює вхідне слово (приписуючи його копію праворуч від самого слова). Нехай - максимальний час її роботи на входах довжини. Доведіть, що для деякого і для всіх. Що можна сказати про, яке є мінімальний час її роботи на входах довжини? p> Розглянемо мова програмування, в якому є всього натуральних змінних, дозволені операції - додавання і віднімання, дозволена перевірка - не дорівнює чи мінлива нулю. Дозволено використовувати if-then-else і while, але рекурсія не вирішена. Доведіть, що за допомогою програм на такій мові програмування можна обчислювати будь-яку обчислюваної функції. p> Побудуйте алгоритм, який визначає, чи є даний базис повним. Базисні функції задані таблицями значень. p> Нехай є максимум складності по всіх булевим функціям від змінних. Доведіть, що при достатньо великих. p> Глибиною схеми називається максимальна кількість елементів на шляху від входів до виходу. Покажіть, що будь-яку функцію можна обчислити схемою глибини не більше з елементів і з елементів і з довільним числом входів. p> Доведіть, що якщо зі схеми глибини, що обчислює функцію, викинути всі несуттєві присвоювання, то отримана схема має поліноміальний по розмір.
Побудуйте схему, яка порівнює два-бітових числа і має розмір, а глибину.
Побудуйте схему складання двох-бітових чисел розміру.
Те ж питання, якщо додатково вимагати, щоб глибина схеми була.
Функція дорівнює 1 на двійкових словах, в яких число одиниць більше числа нулів, і 0 - на інших словах. Побудуйте схему, яка обчислює цю функцію, розмір схеми повинен бути лине по, глибина -. p> Побудуйте схему розміру і глибини, яка перевіряє, чи пов'язані шляхом дві вершини в графі. Граф на вершинах, які позначені числами від 1 до, задається булевими змінними. Мінлива, де, визначає, чи є в графі ребро, що з'єднує вершини і. p> Нехай схема глибини з елементів і з елементів і з довільним числом входів обчислює додавання бітів по модулю (функція). Покажіть, що розмір схеми не менше для деякого. p> Нехай - послідовність булевих функцій від аргументів. Покажіть, що наступні дві властивості рівносильні:
існує послідовність обчислюють ці функції формул, розмір яких не перевершує полінома від;
існує послідовність обчислюють ці функції схем глибини з елементів, і (з двома входами).
Доведіть, що існує розв'язний предикат, який належить, але не належить.
Розділ № ...
