Составители:
Рубрика:
Например, задача 3-выполнимости к.н.ф.: дано множество
дизъюнкций D={d
,d ,…,d
m1 2
} на конечном множестве булевых
переменных X={x
,x ,…,x }, таких, что число |d
n i0 1
| переменных каждой
дизъюнкции равно 3. Требуется ответить на вопрос: существует ли
на X набор значений истинности, при котором выполняются все
дизъюнкции из D?
Предполагается, что для представления исходных данных
используется алфавит Σ и некоторый естественный способ
кодирования Κ, причем длина кода исходных данных задачи z равна
l(z).
*
Введем обозначение Σ
для множества всевозможных цепочек
символов (слов) в алфавите Σ. Любое подмножество множества Σ
*
цепочек называется языком над алфавитом Σ. Множество текстов
задачи Π с ответом из множества Z
п.да
при выбранном способе
кодирования Κ будем рассматривать как язык L(Π,Κ).
Сложность вычислений на машине Тьюринга
Рассмотрим детерминированную машину Тьюринга (ДМТ) M,
вычисляющую рекурсивную функцию
* *
f
: Σ , →Γ
M
*
и Γ
*
где Σ
- множество всевозможных цепочек над алфавитами Σ и Γ
соответственно. При начальной конфигурации q
*
1
σ
, где
σ
∈Σ ,
машина, если когда-либо остановится, завершит работу в
конфигурации q
*
0
γ
, где
γ
= f (
σ
)∈Γ .
M
Число тактов работы для получения
γ
=f
M
(
σ
) назовем временнóй
сложностью машины M и обозначим через t
M
(
σ
). Если значение
f
(
σ
) не определено, то временная сложность t
M M
(
σ
) также не
определена. Активной зоной машины M при работе со входом
σ
называют множество всех ячеек ленты, участвующих в вычислении
γ
=f (
σ
). Длину активной зоны обозачим через s (
σ
).
M M
Теорема 5.1. Если ленточный алфавит машины M содержит k
168
Страницы
- « первая
- ‹ предыдущая
- …
- 82
- 83
- 84
- 85
- 86
- …
- следующая ›
- последняя »
