Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/dfc/2013/Program1/Knop_summary.pdf Дата изменения: Wed Oct 16 17:21:50 2013 Дата индексирования: Fri Feb 28 20:09:14 2014 Кодировка: Windows-1251

Краткое изложение заявки
Кноп Александр Анатольевич
1 Проведенные исследования

Теория сложности вычислений занимается доказательством верхних и нижних оценок для различных моделей вычислений. Наиболее популярным вариантом нижних оценок является нижние оценки в худшем случае, но для прикладных задач (а так же для некоторых теоретических разделов) представляет интерес варианты нижних оценок для сложности задач в среднем. Однако существует несколько определений того, что такое алгоритм работающий полиномиальное время в среднем. Наиболее популярны следующие два варианта определения: первый когда мы разрешаем алгоритму вместо результата возвращать отказ на малой доле входов (относительно некоторого фиксированого распределения), а воторой когда мы разрешаем алгоритму ошибаться и вести себя не корректно на малой доле входов (относительно некоторого фиксированого распределения). Для подобных классов удается доказать многие факты которые не удается доказать для классических классов сложности. Например Первышев [Per07] доказал иерархию по времени для эвристических классов MA и BPP (неизвестную для классических версий этих классов), а Ицыксон [Its09] доказал, что в HeurBPP есть полная задача. Однако не понятна связь этих классов и классических. Например не известно может ли так быть, что P не равно NP, но их эвристические версии все же равны. Импольяци в 2011 [Imp11] году доказал, что этот перенос неравенства не релятивизуется, что существует такой оракул, что c этим оракулом P не равно NP, но эвристические версии все же равны. Для другого определения эвристических вычислений подобный перенос в 2007 году доказали Та-Шма и другие [GSTS07]. Они доказали, что если требовать от алгоритма малой доли ошибок на всех полиномиально сэмплируемых распределениях (а не на одном фиксированном как ранее), то можно доказать, перенос неравенства. Однако для таких классов не известно никаких структурных результатов (которые не известны для классической их версии). Так же для эвристических классов не известно никаких интересных нижних оценок на эвристическую схемную сложность. Самые лучшие известные результаты такого рода (для равномерных классов языков) это мой результат [Kno13] гласящий, что эвристическая схеманя сложность эвристического класса Мерлин-Артур бльше любого фиксированного многочлена, и результат Комаргадского, Раза и Таля [KRT13] гласящий, что существует такая полиномиальная функция f : {0, 1}n 1


{0, 1}, что любая формула Де Моргана размера n 1 входов не большей 2 + 2-(r) .

3-o(1)

/r2 совпадает с f на доле

2

Проект будующих исследований
1. Планируется усилить результат Импольяци и доказать, что
Предположение 2.1.

В моей работе я планирую достичь трех основных результатов:

Для любого

k cуществует такой оракул O, что Distk P

AvgP

Oи

NP P.

2. Планируется усилить уже мой результат про эвристический мэрлин артур и показать, что
Предположение 2.2.

Существует
1 2

HeurMA Heur co -MA Heur

+

1 2-n

a > 0 такое, что для любого k выполнено Size(nk )

3. Усилить наилучшую оценку на схемную сложность класса NP и доказать, что
Предположение 2.3.

NP Size(3n - o(n))

Список литературы
[GSTS07] Dan Gutfreund, Ronen Shaltiel, and Amnon Ta-Shma. If NP languages are hard on the worst-case, then it is easy to nd their hard instances. Computational Complexity, 16(4):412441, 2007. [Imp11] Russell Impagliazzo. Relativized separations of worst-case and average-case complexities for np. In IEEE Conference on Computational Complexity, pages 104114, 2011. Dmitry Itsykson. Structural complexity of AvgBPP. In Proceedings
of the Fourth International Computer Science Symposium in Russia on Computer Science - Theory and Applications

[Its09]

Heidelberg, 2009. Springer-Verlag. [Kno13]

, CSR '09, pages 155166, Berlin,

Alexander Knop. Circuit lower bounds for heuristic ma. Electronic Col loquium on Computational Complexity (ECCC), 20:37, 2013.

[KRT13] Ilan Komargodski, Ran Raz, and Avishay Tal. Improved average-case lower bounds for demorgan formula size. Electronic Col loquium on Computational Complexity (ECCC), 20:58, 2013. [Per07]
Computational Complexity

Konstantin Pervyshev. On heuristic time hierarchies. IEEE Conference of , pages 347358, 2007.

2