Избранное
ЭБ Нефть
и Газ
Главная
Оглавление
Поиск +
Еще книги ...
Энциклопедия
Помощь
Для просмотра
необходимо:


Книга: Главная » Сборник N.N. Проблемы математической логики Сложность алгоритмов и классы вычислимых функций
 
djvu / html
 

260 Ф. К Хенни
брано Fk- Время сравнения для Fk связано с минус-точками и, следовательно, по определению меньше, чем w& — время сравнения для /\. Но в этом есть противоречие, так как Fk было выбрано с наименьшим временем сравнения. Поэтому предположение о том, что каждый пучок может иметь минус-точку, невыполнимо, и некоторый пучок поэтому должен иметь только лишь плюс-точки.
Но если данный пучок имеет только лишь плюс-точки, то каждая точка в пучке должна иметь по крайней мере одну исходящую ветвь, которая отмечена знаком плюс. Поэтому в пучке должен существовать по крайней мере один путь, который включает в себя ветви, отмеченные только плюсом. Выберем в Ац член, базовый сегмент которого соответствует пути от корня дерева до указанного пучка и хвостовой сегмент которого соответствует пути в пучке, который содержит только лишь отмеченные плюсом ветви. Этот член из Ak таков, что М тратит по крайней мере wk единиц времени на каждом его хвостовом блоке и, следовательно, в общем по крайней мере 2hwh единиц времени на всем хвостовом сегменте. Ч. т. д.
Результаты лемм 1 и 2 можно теперь объединить и дать нижнюю границу времени вычисления, необходимого для распознавания множества А.
Теорема 1. Пусть М есть машина со входом, имеющая t лент, s ленточных символов и распознающая множество А. Пусть Т(п) означает максимум количества времени, которое М тратит на всякой входной последовательности длины п. Тогда Т(п) превышает
48/ log s log2 n
для достаточно больших значений п.
Доказательство. Нам нужно рассмотреть только лишь случай, в котором М работает с границей я2, так как иначе утверждение теоремы будет безусловно правильным. Пусть nh означает общую длину последовательностей в множестве Ak, и пусть Th означает максимум времени, которое М должна потратить на последовательностях из Л&. Тогда для всякого данного значения п выберем k таким, чтобы nk^n^,nh+\. Так как время вычисления, нужное машине М, монотонно по п, то Г(я)> 7\, в то время как по леммам 2 и 1 мы имеем, что
*я, - 2fe(2*-logQ~Mogs-l) Wk>----------

 

1 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 180 190 200 210 220 230 240 250 260 261 262 263 264 265 266 267 268 269 270 280 290 300 310 320 330 340 350 360 370 380 390 400 410 420 430


Математика