Кузюрин Н.Н. Фомин С.А. Эффективные алгоритмы и сложность вычислений

Подождите немного. Документ загружается.

321

навливаются, будучи запущенными на пустой ленте.

Задача № 6.1.8 на странице 215

Существует ли алгоритм, который выписывает одну за дру-

гой все машины Тьюринга, которые останавливаются, будучи

запущенными на пустой ленте?

Задача № 6.1.9 на странице 215

Докажите, для разрешимых языков L

и L

, язык L = L

∪L

также разрешим.

Задача № 6.1.10 на странице 215

Пусть M — машина Тьюринга с единственной лентой, ко-

торая копирует входное слово (приписывая его копию справа

от самого слова). Пусть T (n) — максимальное время ее работы

на входах длины n. Докажите, что T (n) ≥ εn

для некоторо-

го ε и для всех n. Что можно сказать про T

(n), которое есть

минимальное время ее работы на входах длины n?

Задача № 6.1.11 на странице 215

Пусть T (n) — максимальное время, которое может пройти

до остановки машины Тьюринга с n состояниями и n симво-

лами алфавита, если ее запустить на пустой ленте. Докажите,

что. функция T (n) растет быстрее любой вычислимой всюду

определенной функции b(n), то есть lim[T(n)/b(n)] = +∞.

Задача № 6.1.12 на странице 215

Докажите, что разрешим язык L, состоящий из n ∈ N, та-

ких, что строка «4815162342» встречается в десятичном разло-

жении числа π не менее чем n раз подряд.

322 Глава 8. Сборник упражнений (ИСПРАН-2008-весна)

Тема: dtime-dspace

Задача № 6.1.13 на странице 217

Дан неориентированный граф G = (V, E), и вершины s

и t. Придумайте алгоритм с пространственной сложностью

O(log n) (n-длина входа), который возвращает «1», если есть

путь из s в t длиной не больше 777 log n, проходящий только

через вершины имеющие не больше 777 соседей, и «0» в про-

тивном случае.

Задача № 6.1.14 на странице 219

Рассмотрим язык L состоящий из слов hM, x, ti, для кото-

рых ДМТ M останавливается на x не позже, чем через t шагов.

Докажите: L ∈ EX PT IME.

Задача № 6.1.15 на странице 220

Покажите, что P ⊆ EX PT IME.

Задача № 6.1.16 на странице 220

Покажите, что PSPACE ⊆ EX PT IME.

Задача № 6.1.17 на странице 220

LOGSP ACE = DSP ACE(O(log n)).

Покажите, что LOGSP ACE ⊆ P.

323

Задача № 6.1.18 на странице 220

LOGSP ACE = DSP ACE(O(log n)).

Рассмотрим язык «правильно вложенных скобок» L:

∈ L (), ()()((())()), (()()(())), . . .

/∈ L )(, . . .

Докажите, что L ∈ LOGSP ACE.

Тема: p-reducibility-and-npc

Задача № ?? на странице ??

Задача № 6.2.1 на странице 226

Покажите, что P ⊆ N P ∩ coN P.

Задача № 6.2.2 на странице 235

Выразите логическое отношение эквивалентности в виде 3-

КНФ формулы.

Задача № 6.2.3 на странице 235

Рассмотрим ограниченную версию задачи 28 «3SAT», где

на КНФ-формулу дополнительно наложено ограничение, что

в ней каждая переменная может входить не больше трех раз,

причем каждый литерал — не больше двух.

Покажите, что и эта задача NP-полна.

324 Глава 8. Сборник упражнений (ИСПРАН-2008-весна)

Задача № 6.2.4 на странице 235

Покажите, что задача 29 «2SAT» лежит в P.

Задача № 6.2.5 на странице 236

Рассмотрим максимизационную версию задачи 29 «2SAT»,

где дополнительно к 2SAT -формуле задается параметр K, и

спрашивается, можно ли выполнить больше чем K, количество

скобок.

Покажите, что эта задача лежит в N PC.

Задача № 6.2.6 на странице 239

Покажите, что задача распознавания гамильтоновых гра-

фов (т. е. графов, содержащих гамильтонов цикл) принадле-

жит N P, а задача распознавания негамильтоновых графов

принадлежит coN P.

Задача № 6.2.7 на странице 239

Придумайте полиномиальный алгоритм для проверки, есть

ли в заданном графе хотя бы один «треугольник».

Задача № 6.2.8 на странице 239

Рассмотрим язык DF NT , состоящий из полиномов от

нескольких переменных, имеющих целочисленные корни.

Студент утверждает, что DF NT ∈ NP , т.к. если оракул-

Мерлин предоставит решение v, доказывающее принадлеж-

ность полинома p ∈ DF NT , то верификатор Артур сможет

легко проверить: p(v)

= 0.

Прав ли студент?

325

Тема: randomized-compexity

Задача № 6.3.1 на странице 252

Вы разработчик военного программного комплекса, ис-

пользующего сложновычислимую и секретную функцию

F : [0, . . . , N − 1] → [0, . . . , m − 1], которую подключают к

вашему алгоритму в виде отдельного массива длины N , т. е.

функция задана таблично на внешней флеш-памяти огромно-

го объема(только вес этой флэшки — 20 кг, которую носят и

охраняют два майора-особиста). Функция гомоморфна, т. е.

F ((x + y) mod N) = (F (x) + F (y)) mod m

Однако, утром перед приемными испытаниями, выясни-

лось, что «флешка побилась», т. е. некоторые значения этой

функции стали неверными. Виновные майоры уже расстреля-

ны, а вся команда разработчиков пытается решить проблему.

Инженеры исследовали сбой — и утверждают, что «поби-

лось» не более

ячеек, к сожалению, неизвестно каких.

С учетом этого факта вам поставлена задача реализовать

простой и быстрый алгоритм, который правильно вычисляет

F (x) с вероятностью не меньше

Задача № 6.3.2 на странице 253

Все то же, что и в упражнении 6.3.1, но чтобы вероят-

ность ошибки P

err

можно было сделать произвольно малой,

т. е. 2

−p(|x|)

, и при этом, чтобы выполнение алгоритма было за-

медлено не больше, чем в O(p(|x|)) раз.

Задача № 6.3.3 на странице 253

326 Глава 8. Сборник упражнений (ИСПРАН-2008-весна)

Вводная, что и в упражнении 6.3.1, только теперь достаточ-

но времени (испытания прошли, есть пара недель перед вводом

в опытную эксплуатацию), и нужно восстановить значение этой

функции за время O(N

Задача № 6.3.4 на странице 254

Что будет, если в определении 6.3.14 в обоих неравенствах

поставить «≥»? Какой класс языков будет определен?

Задача № 6.3.5 на странице 259

Класс сложности ZPP

NotNull

состоит из всех языков L, для

которых существует ВМТ M, всегда возвращающая правиль-

ные ответы (т. е. никаких «не знаю»), причем ∃ полином p(n),

что для времени работы T

(x) машины M выполняется:

E T

(x) ≤ p(|x|).

Докажите, что ZPP

NotNull

= ZPP.

Тема: diagram-complexity-classes

Задача № 6.6.1 на странице 298

Покажите, что если N P ⊆ coRP, то NP ⊆ coZPP.

Список литературы

[67] . Хартманис, . Стирнз. О вычислительной слож-

ности алгоритмов // Киб. сборник, нов. сер. № 4.

М., Мир, 1967. с. 57–85.

[Кар75a] .. Карп. Сводимость комбинаторных задач // Киб.

сборник, нов. сер. / под редакцией . СССР. № 12.

1975. с. 16–38.

[Кук75b] C.. Кук. Сложность процедур вывода теорем //

Киб. сборник, нов. сер. / под редакцией . Мир. № 12.

1975. с. 5–15.

[79] . Ахо, . Хопкрофт, . Ульман. Построение и анализ

вычислительных алгоритмов. М.: Мир, 1979.

[82] . Гэри, .. Джонсон. Вычислительные машины и

труднорешаемые задачи. М.: Мир, 1982.

[Раз85a] .. Разборов. Нижние оценки монотонной сложно-

сти логического перманента // Математические

Заметки. 1985. Т. 37, № 4. с. 887–900.

[Раз85b] .. Разборов. Нижние оценки размера схем

ограниченной глубины в полном базисе, со-

держащем функцию логического сложения. //

Математические Заметки. 1985. Т. 37, № 6.

[Схр91] . Схрейвер. Теория линейного и целочисленного

программирования. М. Мир, 1991.

328 Список литературы

[96] .. Кузюрин, .. Разборов. Оценка состояния и про-

гнозные исследования эффективных алгоритмов

для точного и приближенного решения перебор-

ных задач дискретной оптимизации: Отчет по НИР:

Математический институт им. В.А. Стеклова РАН,

Москва, 1996.

[99a] . Кормен, . Лейзерсон, . Ривест. Алгоритмы: по-

строение и анализ. М.: МЦНМО, 1999.

[99b] . Китаев, . Шень, . Вялый. Классические и кванто-

вые вычисления. Издательство МЦНМО, 1999.

http://www.mccme.ru/free-books/

[Суз06] . Сузи. Язык программирования Python. Интернет-

университет информационных технологий —

ИНТУИТ.ру, 2006.

[Суз07] . Сузи. Курс ИНТУИТ: Язык программирования

Python. 2007.

http://www.intuit.ru/department/pl/python/

[Aar07] S. Aaronson. Complexity Zoo, Wiki-review of com-

plexity classes. 2007.

http://qwiki.stanford.edu/wiki/Complexity_Zoo

[AS92] N. Alon, J. Spencer. The Probabilistic Method.

Wiley, 1992.

[Blu67] M. Blum. A Machine-Independent Theory of the

Complexity of Recursive Functions // Journal of the

ACM. 1967. Vol. 14, no. 2. pp. 322–336.

[BV03] R. Beier, B. V¨ocking. Random Knapsack in Expected

Polynomial Time // Proceedings of the 35th ACM

Symposium on Theory of Computing (STOC). 2003.

pp. 232–241.

http://citeseer.ist.psu.edu/beier03random.html

Список литературы 329

[Chu36] A. Church. An Unsolvable Problem of Elementary

Number Theory // American Journal of Mathematics.

1936. Vol. 58, no. 2. pp. 345–363.

[CK] P. Crescenzi, V. Kann. A compendium of NP opti-

mization problems.

http://www.nada.kth.se/viggo/problemlist/compendium.html

[CW90] D. Coppersmith, S. Winograd. Matrix multiplica-

tion via arithmetic progressions // J. Symb. Comput.

1990. Vol. 9, no. 3. pp. 251–280.

[Fei98] U. Feige. A Threshold of ln n for Approximating Set

Cover // Journal of the ACM. 1998. Vol. 45, no. 4.

pp. 634–652.

http://citeseer.ist.psu.edu/feige95threshold.html

[Fre77] R. Freivalds. Probabilistic Machines Can Use Less

Running Time // IFIP Congress. 1977. pp. 839–842.

[GLST98] A Tight Characterization of NP with 3 Query PCPs //

IEEE Symposium on Foundations of Computer

Science. 1998. pp. 8–17.

http://citeseer.ist.psu.edu/guruswami98tight.html

[Gol99] O. Goldreich. Complexity Theory: lecture notes.

1999.

http://www.wisdom.weizmann.ac.il/

oded/cc.html

[GW94] M. Goemans, D. Williamson. New 3/4-approximation

algorithms for MAX SAT // SIAM Journal on

Algebraic and Discrete Methods. Vol. 7. 1994.

pp. 656–666.

http://citeseer.ist.psu.edu/goemans94new.html

[GW95] M.X. Goemans, D.P. Williamson. Improved

Approximation Algorithms for Maximum Cut

330 Список литературы

and Satisﬁability Problems Using Semideﬁnite

Programming // J. Assoc. Comput. Mach. 1995.

Vol. 42. pp. 1115–1145.

http://citeseer.ist.psu.edu/goemans95improved.html

[H˚as97] J. H˚astad. Some optimal inapproximability results //

STOC’97: Proceedings of the twenty-ninth annual

ACM symposium on Theory of computing. New York,

NY, USA: ACM Press, 1997. pp. 1–10.

[Hoa62] C.A.R. Hoare. Quicksort // Computer Journal. 1962.

Vol. 5, no. 1. pp. 10–15.

[IM02] K. Iwama, H. Morizumi. An Explicit Lower Bound

of 5n − o(n) for Boolean Circuits // Proc. of the

27th Int. Symp. on Math. Foundations of Computer

Science. 2002. Vol. 2420. pp. 353—364.

http://link.springer.de/link/service/series/0558/papers/

2420/24200353.pdf

[Iwa89] K. Iwama. CNF satisﬁability test by counting and

polynomial average time // SIAM J. Comput. 1989.

Vol. 18, no. 2. pp. 385–391.

[Joh73] D.S. Johnson. Approximation algorithms for combi-

natorial problems // STOC ’73: Proceedings of the

ﬁfth annual ACM symposium on Theory of computing.

New York, NY, USA: ACM Press, 1973. pp. 38–49.

[Joh90] D.S. Johnson. A Catalog of Complexity Classes //

Handbook of Theoretical Computer Science, Volume

A: Algorithms and Complexity (A). MIT Press, 1990.

pp. 67–161.

[Kar84] N. Karmarkar. A New Polynomial-Time Algorithm

for Linear Programming // Combinatorica. 1984.

Vol. 4, no. 4. pp. 373–395.