В.А. Носов - Основы теории алгоритмов и анализа их сложности (курс лекций), страница 15

Пусть головкамашины Т пересекает границу j точно s раз: в первый раз в состоянии q(1) , вовторой раз в состоянии q(2) и т.д. Тогда последовательность q(1)q(2)...q(2) ,являющаяся словом в алфавите внутренних состояний машины Т , называетсяследом вычисления T[ P ] в точке j и обозначается trT ( P , j ) .Если рассматриватьконечные процессы T[ P ] , то и следы будут конечные. Ясно, чтопересечение головкой какой-либо границы связано с затратой одного тактаработы машины, поэтому справедливо неравенствоtT ( P) ≥ ∑ trT ( P , j )(1)где сумма берется по любому множеству границ j.

(Через Q обозначаем длинуслова Q. Неравенство (1) может дать нижнюю оценку времени вычисления, еслииметь нижнюю оценку для длин следов.30 ) Справедлива следующаяТеорема 1.Пусть Т - произвольная машина Тьюринга, решающая проблему симметриислов, имеющая k внутренних состояний. Тогда для любого ε > 0 справедливаоценка 1− ε2tT ( P ) = ΩP  4 log 2 kдля почти всех симметричных слов. (Знак Ω означает нижнюю оценку попорядку)Замечание.Говорят, что почти все слова, обладающие свойством R, обладают и свойствомS , еслиS R ( n)→ 1 при n → ∞ , где R(n) - число слов длины n,R ( n)обладающих свойством R. S R (n) - число слов длины n , которые обладаютнаряду со свойством R также свойством S.Док-во.Пусть даны два симметричных слова Р1 и Р2 длины n = 2η (в случае нечетного nрассуждения аналогичны) и пусть они имеют разные начала длины ξ .

В такомслучае следы в точке ξ различны, т.е. trT ( P1 , j ) ≠ trT ( P2 , j ) .Допустим противное и пусть trT ( P1 , j ) = trT ( P2 , j ) .Для слов Р1 и Р2 обозначимP1ξ начало слова Р1, длины ξ , ξ P2 слово полученное из Р2 удалением началаξдлины ξ . Образуем слово P1 ξ P2 . По условию слово R не симметрично, Еслизапустить машину Т со словом на ленте, то левее ξ оно будет обрабатыватьсякак Р1 , а правее ξ - как Р2 и в силу симметричности Р1 и Р2,машина Т выдаст 1,что противоречит тому, что R не симметрично.84Зафиксируем некоторое ξ ∈1, n и разобьем множество всех симметричныхслов длины n = 2η мощности на классы, в каждом из которых все слова имеютодинаковые начала длины ξ , а слова из разных классов имеют разные началадлины ξ .

Таких классов, очевидно, 2ξ - по числу различных слов длины ξ вкаждом классе имеется 2η − ξ слов. Слова из разных классов по доказанному,обязаны иметь в точке ξ попарно различные следы. Выберем из каждого классапо одному представителю с наиболее коротким следом в точке ξ . Значитсуществует 2ξ попарно различных следов,которые являются словами в алфавитеиз К букв. Пусть дано ε > 0 определим, сколько среди 2ξ следов может быть"коротких" следов, т.е. следов, имеющих длину, не превышающую(1 − ε ) log k 2ξ =2k + k +...+ k1− εξ .Ясно, что "коротких" следов не более, чемlog 2 k (1− ε ) ξlog 2 k =k (1− ε )log 2 k k −1+1≤k (1− ε )log 2 k + 1 = k 2 (1− ε )ξОтсюда получаем» что число симметричных слов, у которых в точке ξ"короткий' след,не превосходитk 2 (1− ε )ξ 2η − ξ = k 2η − εξ .Обозначим через ∆(ε , ξ ) долю симметричных слов, у которых в точке ξ1− εk 2η − εξk"короткий" след (т.е.

след длины ≤ξ ).Имеем ∆(ε , ξ ) ≤.=ηε ξlog 2 k2(2 )Обозначая α = 1 ε , имеем 0 < α < 1 и ∆(ε , ξ ) ≤ kα ξ .2Пусть ω (η) - любая функция (например, log η ), обладающая свойствами1) ω (η) → ∞ при η → ∞ω (η)→ ∞ при η → ∞2)ηОбозначим через ∆(ε ) долю тех симметричных слов, для которых существуетξ , такое, что ω (η) < ξ < η и в точке ξ - "короткий" след. Имеем∆( ε ) ≤ ∆( ε , ω (η )) + ∆( ε , ω (η ) + 1) + ∆( ε , η ) =α ω ( η ) − α η +1ω (η )ω ( η )+1η+α+...+α ) = k= k (α1− αПри η → ∞ имеем ∆( ε ) → 0 для любого ε > 0 .

В этом смысле говорят, чтопочти все симметричные слова имеют в точках между ω (η ) и η "длинные"следы. Сумма длин следов на левой половине почти для всякого симметричногослова больше, чем1− ε(ω (η ) + (ω (η ) + 1)+...+η) =log 2 k85=1 − ε η + ω (ω )⋅(η − ω (ω )) =2log 2 k1 − ε η 2 − ω (η ) 1 − ε η 2=⋅≈2log 2 klog 2 k 2приη →∞Это означает, что время нахождения считывающей головки на левой половинеслова Р по порядку не меньше, чем1 − ε η2(для почти всех слов Р ).log 2 k 2Аналогичная картина имеет место для правой половины слова Р в итогеполучаем: 1 − ε η2 1− ε2=tT ( P ) = ΩP log 2 k 2  4 log 2 kч.т.д.Поскольку указывалась машина Тьюринга, имеющая верхнюю оценку( ) , то полученная в теореме 1 нижняя оценкавремени вычисления tT ( P ) = O P2является асимптотически оптимальной.Замечание.Вместо проверки симметрии слова можно рассмотреть задачу проверки ( ϕ-симметрии, которая ставится так.

Пусть задана функция ϕ ( n ) ≤n, n ∈N .2, ϕ -симметрично, еслиБудем говорить, что слово P ( P = n в алфавите E = 01его концы длины ϕ ( n ) симметричны. Может быть доказанаТеорема2.Для любой функции ϕ ( n ) , удовлетворяющей условиям log 2 n p ϕ ( n ) p n(неравенство по порядку) и для любой машины Тьюринга Т с k состояниями,распознающей ϕ -симметрию , и для любого ε > 0 имеет место 1− εtT ( n ) = Ωnϕ ( n ) (неравенство по порядку) log 2 k4 0 ) Техника следов может быть применена для получения нижних оценоквременной сложности решения других задач.

Рассмотрим некоторые из них.1) Пусть Р - слово в алфавите E = 01, . Слово Р является точнымквадратом, если Р=Р1Р1 для некоторого слова Р1. Рассмотрим задачу: Дляпроизвольного слова узнать, является ли оно точным квадратом. Легкопроверить,что для данной задачи справедлива теорема 1.2) Для произвольного n рассмотрим множество слов Р длины 2 n в алфавитеE = 01, и будем их трактовать как таблицы булевых функций f ( x1,..., x n ) при86лексикографическом упорядочении множества аргументов.Рассмотримзадачи:а) Существенность 1-го переменного: по слову Р узнать, является ли переменноеx1 существенным.б) Существенность n-го переменного: по слову Р узнать, является ли переменноеxn существенным.Легко проверить, что для задачи а) справедлива теорема 1, а задача б) решаетсяза линейное время, т.е.tT ( P ) = O ( P )в) функциональная полнота: по слову Р, P = 2 n узнать, является лисоответствующая булева функция f ( x1, ..., x n ) Шефферовой (т.е.

представляетли она функционально полную систему функций). Можно доказать, что дляданной задачи справедлива теорема 1. Более того, может быть доказаносуществование машины Тьюринга, проверяющей критерий функциональной2полноты Поста за время O ( P ) и, следовательно, квадратичная оценка являетсяасимптотически оптимальной., и3) Для произвольного n рассмотрим слово Р длины n2 n в алфавите E = 01будем трактовать его как табличное задание семейства булевых функцийf1 ( x1,..., x n ),..., f n ( x1,..., x n ) при лексикографическом упорядочении множествапеременных.

Рассмотрим задачу: по слову Р, P = n2 n узнать, является лисоответствующее семейство булевых функций биективным. Может бытьдоказанаТеорема 3.Пусть Т - машина Тьюринга с k внутренними состояниями, которая решаетзадачу биективности семейства булевых функций. Тогда для любого ε > 0справедлива оценка 1− εt ( P ) = Ωn 22 n  4 log 2 kдля почти всех регулярных семейств ( f1,..., f n ) (Неравенство по порядку)Заметим, что в данном случае оценка не является квадратичной, т.к. длинавходного слова P есть n2 n .87§ 14.

Классы сложности P и NP и их взаимосвязь1°. Установление прямых нижних оценок сложности вычислений, о которых шларечь в предыдущем разделе, удается лишь в очень редких случаях. В связи сэтим получил распространение подход, связанный с получением косвенныхнижних оценок, т.е. установление таких утверждений, в которых существованиеэффективного разрешающего алгоритма для конкретной задачи влечет за собойсуществование эффективного алгоритма для многих общепризнанно трудныхзадач.Нам необходимо формализовать соответствующий подход. Пусть П некоторая массовая задача, характеризуемая множеством параметров, I∈П индивидуальная задача, в которой эти параметры фиксированы.

Пусть смассовой задачей П связана и зафиксирована схема кодирования α, котораяставит каждой индивидуальной задаче I∈П в соответствие слово α(I) внекотором алфавите A. При этом под размером задачи I понимается длина словаα(I). Пусть Т - машина Тьюринга, решающая задачу П иtT ( n) = max tT ( I )(1)I,α ( I ) = n- соответствующая функция временной сложности (по худшему случаю).Говорят, что машина T решает задачу П за полиномиальное время, еслиtT ( n) =O(p(n))(2)для некоторого полинома р.В противном случае говорят, что машина T решает задачу П заэкспоненциальное время. Заметим, что при данном определении кlog nэкспоненциальным оценкам относятся, например, оценки вида O( n 2 ) .(Некоторые авторы оценки такого вида называют субэкспоненциальными, подкоторыми понимают такие оценки, которые превосходят любой полином, ноεменьше, чем O(2n ) для любого ε>0).Про задачу П говорят, что она разрешима за полиномиальное время, еслисуществует машина Тьюринга Т, решающая ее за полиномиальное время.Обозначим через P класс задач, разрешимых за полиномиальное время.Относительно класса P необходимо сделать следующие замечания.1) В определении класса Р существенным является фиксация схемыкодирования α.

Многие естественные схемы кодирования полиномиальноэквиваленты, т.е. позволяют переходить от одного кода задачи к другому коду заполиномиальное время от длины кода. В этом случае принадлежность (или непринадлежность) задачи П классу Р определяется инвариантно по отношению ксхемам кодирования. Однако, это справедливо не всегда и, вообще говоря, класссложности Р зависит от схемы кодирования, поэтому там, где схема кодированияне очевидна или может повлиять на класс сложности, ее следует указывать явно.2) Класс Р определен через функцию временной сложности машиныТьюринга. Можно сделать соответствующие определения через любую другуюалгоритмическую модель.88Однако, имеется ряд фактов о полиномиальной эквивалентностивременных функций сложности многих типов вычислительных моделей, чтопозволяет утверждать, что класс Р определен однозначно для "разумных"вычислительных моделей.

С результатами взаимного моделированиявычислительных моделей можно ознакомиться в [2],[15]. Поэтому безспециальных оговорок будут допускаться выражения типа “алгоритм А имеетполиномиальную сложность” или “алгоритм B имеет экспоненциальнуюсложность”. Обратим внимание, что имеется существенное различие междуалгоритмами полиномиальной и экспоненциальной сложности. Ясно, что любойполиномиальный алгоритм более эффективен при достаточно больших размерахвхода. Кроме того, полиномиальные алгоритмы лучше реагируют на ростпроизводительности ЭВМ.