А.А. Сапоженко - Некоторые вопросы сложности алгоритмов (PDF) (1132758), страница 8
Текст из файла (страница 8)
Построенная нами схема из обобщенных элементов моделирует работу машины M . Фактически она воспроизводит последовательность конфигураций при работе машины над входным словом. Из построенияясно, что схема содержит 2T 2 обобщенных элементов. После замены каждоготакого элемента схемой из двоичных элементов сложность возрастает тольков константу раз.2Примечание. Легко видеть, что в построенной схеме много ”лишних”элементов. Это, например, элементы правого верхнего угла схемы, где длительное время состояние остается холостым.
И в оставшейся части схемы существенны только элементы в окрестности нехолостого значения состояния.Это предоставляет большие возможности для упрощения схемы. К.П.Шнорр[3] понизил верхнюю оценку до O(TM (n) log SM (n) + kM k), где TM (n) и SM (n)соответственно число тактов и число ячеек, достаточное для обработки словадлины n машиной Тьюринга, а kM k — число команд машины M .Список литературы[1] J.E.Savage, Computational work and time on finite machines, J.
Ass. Comp.Mach., 1972, v. 19, p. 660-674.[2] Р.Г.Нигматуллин, Сложность булевых функций, Издательство Казанского университета, 1983, 208 c.[3] C.P.Schnorr, The network complexity and the Turing machine complexity offinite functions. Acta Informatica, 1976, v. 7, p. 95-107.40Содержание1.2.3.4.5.6.7.ВведениеАлгоритмические трудности синтеза схемЛокальные алгоритмыТеорема КукаN P -полнота задач k-ВЫПНекоторые N P -полные задачиТеорема Сэвиджа41241019243037.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
