Викиконспекты - Вклад участника [ru]

Класс PS. Связь класса PS с другими классами теории сложности

2012-06-04T22:38:07Z

178.178.4.118: смерть пережиткам прошлого

== Определение ==
{{Определение
|definition=<tex>\mathrm{PS}</tex> <tex>\mathrm{(PSPACE)}</tex> {{---}} класс языков, разрешимых на детерминированной машине Тьюринга с использованием памяти полиномиального размера. <br>
<tex>\mathrm{PS}=\bigcup\limits_{p(n) \in poly} \mathrm{DSPACE}(p(n))</tex>.
}}

{{Определение
|definition=<tex>\mathrm{NPS}</tex> <tex>\mathrm{(NPSPACE)}</tex> {{---}} класс языков, разрешимых на недетерминированной машине Тьюринга с использованием памяти полиномиального размера. <br>
<tex>\mathrm{NPS}=\bigcup\limits_{p(n) \in poly} \mathrm{NSPACE}(p(n))</tex>.
}}

== Связь класса PS с другими классами теории сложности ==
{{Теорема
|statement =
<tex>\mathrm{P} \subseteq \mathrm{PS}</tex>.
|proof = Рассмотрим любой язык <tex>L</tex> из <tex>\mathrm{P}</tex>. Так как <tex>L \in \mathrm{P}</tex>, то существует машина Тьюринга <tex>m</tex>, распознающая <tex>L</tex> за полиномиальное время. Это значит, что <tex>m</tex> не сможет использовать более, чем полиномиальное количество памяти, следовательно <tex> L \in \mathrm{PS}</tex>.
}}

{{Теорема
|statement =
<tex>\mathrm{NP} \subseteq \mathrm{PS}</tex>.
|proof = Рассмотрим любой язык <tex>L</tex> из <tex>\mathrm{NP}</tex>. Так как <tex>L \in \mathrm{NP}</tex>, то существует программа-верификатор <tex>R(x,y)</tex>, что для каждого слова из <tex>L</tex> (и только для них) существует такой сертификат <tex>y</tex> полиномиальной длины, что <tex>R</tex> допускает слово и сертификат. Тогда, чтобы проверить принадлежность слова языку, мы можем перебрать все сертификаты полиномиальной длины. Для этого необходим полиномиальный размер памяти. Из этого следует, что <tex>L \in \mathrm{PS}</tex>.
}}

Теория сложности

2012-06-04T16:14:14Z

178.178.4.118:

{{В разработке}}

[[Категория: Теория сложности]]

== Детерминированные и недетерминированные вычисления, сложность по времени и по памяти ==
*[[Сложностные классы. Вычисления с оракулом]]

=== Классы P и NP, NP-полнота ===
*[[Класс P]]
*[[Недетерминированные вычисления]]
*[[Классы NP и Σ₁]]
*[[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи]]
*[[Примеры NP-полных языков. Теорема Кука]]
*[[Теоремы о временной и емкостной иерархиях]]
*[[Теорема Бейкера — Гилла — Соловэя]]
*[[Теорема Ладнера]]
*[[Теорема Левина]]
*[[Теорема Бермана — Форчуна]]
*[[Теорема Махэни]]

=== Сложность по памяти, классы PS, L, NL, coNL ===
*[[Класс PS. Теорема Сэвича. Совпадение классов NPS и PS]]
*[[PS-полнота языка верных булевых формул с кванторами (TQBF)]]
*[[Классы L, NL, coNL. NL-полнота задачи о достижимости]]

=== Полиномиальная иерархия ===
*[[Классы PH, Σ и Π]]
*[[Теоремы о коллапсе полиномиальной иерархии]]

== Схемная сложность ==
*[[Схемная сложность и класс P/poly]]
*[[Теорема Карпа — Липтона]]
*[[Классы NC и AC]]
*[[Теорема о непринадлежности XOR классу AC⁰]]

== Вероятностные сложностные классы ==
*[[Вероятностные вычисления. Вероятностная машина Тьюринга]]
*[[Классы BPPweak и BPPstrong]]
*[[Уменьшение ошибки в классе RP]]
*[[Теорема Лаутемана]]

=== Интерактивные протоколы ===
*[[Интерактивные протоколы. Класс IP. Класс AM]]
*[[Связь классов IP и AM друг с другом и с другими классами языков]]
*[[Арифметизация булевых формул с кванторами]]
*[[Лемма о соотношении coNP и IP]]
*[[Теорема Шамира]]
*[[Семейство универсальных попарно независимых хеш-функций]]
*[[Протокол Голдвассера-Сипсера для оценки размера множества]]

=== Probabilistically checkable proofs ===
*[[PCP-система]]
*[[PCP-теорема]]
*[[PCP-теорема, альтернативное доказательство | PCP-теорема, альтернативная формулировка]]

----

[[Теория сложности (старая трешовая версия)|Вот сюда]] можно подсматривать, но злоупотреблять не рекомендуется.

Классификация задач

2012-06-04T15:04:15Z

178.178.4.118:

==Нотация Грэхема==
<tex> \alpha </tex> | <tex> \beta </tex> | <tex> \gamma </tex>

Поле <tex> \alpha </tex> описывает тип обработки. Задается одним значением.

Поле <tex> \beta </tex> описывает характеристики работ. Задает параметры работ, и то, какими свойствами должно обладает расписание.

Поле <tex> \gamma</tex> описывает критерий оптимизации. Содержит функцию, которую нужно оптимизировать.

==Типы обработки==
{{Определение
|definition =
'''Одна машина''' (Single machine, '''1''') В системе находится одна машина.}}

{{Определение
|definition =
'''Параллельные одинаковые машины''' (Parallel and Identical Machines, '''<tex>P_{m}</tex>''') В системе находится m одинаковых машин, работающих параллельно.}}

{{Определение
|definition =
'''Параллельные однородные машины''' (Uniform Machines, '''<tex>Q_{m}</tex>''') В системе находится m машин, работающих параллельно. У машин разные скорости выполнения работ.}}

{{Определение
|definition =
'''Параллельные несвязанные машины''' (Unrelated Machines, '''<tex>R_{m}</tex>''') В системе находится m машин, работающих параллельно. У машин разные скорости выполнения разных работ.}}

{{Определение
|definition =
'''Job shop''' ('''<tex>J_{m}</tex>''') В системе находится m машин, работающих параллельно. У каждой работы свой упорядоченный список машин, на которых они должны быть выполнены.}}

{{Определение
|definition =
'''Flow shop''' ('''<tex>F_{m}</tex>''') В системе находится m машин, работающих параллельно. Машины упорядочены. Работы должны выполняться сначала на первой машине, потом на второй и т.д. до последней.}}

{{Определение
|definition =
'''Open shop''' ('''<tex>O_{m}</tex>''') В системе находится m машин, работающих параллельно. Каждая работа должна быть выполнена один раз на каждой машин. Порядок не важен}}

==Характеристики работ==
{{Определение
|definition =
'''Время работы''' (Processing time, <tex>p_{i,j}</tex>) Если работа j выполняется на машине i, то <tex>p_{i,j}</tex> является временем обработке работы j на машине i}}

{{Определение
|definition =
'''Время появления''' (Release date, <tex>r_{j}</tex>) <tex>r_{j}</tex> является временем появления в системе работы j, минимальное время в которое можно начать обработку работы j}}

{{Определение
|definition =
'''Время окончания''' (Due date, <tex>d_{j}</tex>) <tex>d_{j}</tex> является временем до которого ожидается выполнения работы j. Если работа j была выполнена после <tex>d_{j}</tex>, то налагается штраф}}

{{Определение
|definition =
'''Дедлайн''' (Deadline, <tex>d_{j}</tex>) Тоже самое что и время окончания, но после дедлайна выполнять работу нельзя.}}

{{Определение
|definition =
'''Вес''' (Weigth, <tex>w_{j}</tex>) Величина отражающая значение работы j.}}

{{Определение
|definition =
'''Прерывание''' (Preemption, <tex>pmtn</tex>) Работа может быть прервана и продолжена позже.}}

{{Определение
|definition =
'''Зависимость между работами''' (Precedence Contraints, <tex>prec</tex>) {Работа может начаться только после выпонения некоторых других работ. Может быть представлено ввиде ориентированного графа. При этом каждой вершине соответствует работа и работа i выполняется перед работой j, если есть ребро из вершины i в j.
*''chains'' <tex>{-}</tex> в каждую вершину входит не более одного ребра и выходит не более одного ребра
*''intree'' <tex>{-}</tex> из вершины выходит не более одного ребра
*''outtree'' <tex>{-}</tex> в вершину входит не более одного ребра
}}

==Критерий оптимизации==

{{Определение
|definition =
'''Цель оптимизации''' минимизировать тот или иной критерий.}}

{{Определение
|definition =
'''Время окончания работы''' (Completion time, <tex>C_{j}</tex>) Время окончания обработки работы j.}}

{{Определение
|definition =
'''Опоздание''' (Lateness, <tex>L_{j}</tex>) .<tex>L_{j}</tex> = <tex>C_{j}</tex> - <tex>d_{j}</tex>}}

{{Определение
|definition =
'''Опоздание''' (Tardiness, <tex>T_{j}</tex>) .<tex>T_{j}</tex> = <tex>max(L_{i}, 0)</tex>}}

{{Определение
|definition =
'''Штраф''' (Unit penalty, <tex>U_{j}</tex>) . Если <tex>C_{j}</tex> > <tex>d_{j}</tex>, то <tex>U_{j}</tex> = 1, иначе <tex>U_{j}</tex> = 0 }}

{{Определение
|definition =
'''Опоздание''' (Tardiness, <tex>L_{j}</tex>) .<tex>T_{j}</tex> = <tex>max(L_{i}, 0)</tex>}}

==Источники==
*[http://books.google.ru/books?id=MAY1ZstmGPkC&dq=HandBook+of+Scheduling&hl=ru&sa=X&ei=O8PMT8nYEKjh4QTKgsHsBw&ved=0CDMQ6AEwAA Handbook of scheduling: algorithms, models, and performance analysis, Joseph Y-T. Leung ]
*[http://books.google.ru/books?id=FrUytMqlCv8C&printsec=frontcover&dq=scheduling+algorithms&hl=ru&sa=X&ei=0MPMT4HqKYSk4gSBm6gp&sqi=2&ved=0CDEQ6AEwAA#v=onepage&q=scheduling%20algorithms&f=false Scheduling Algorithms, Peter Brucker]

Обсуждение:Недетерминированные вычисления

2012-06-04T14:48:25Z

178.178.4.118:

Какая мощность может быть у правой части оператора <tex>\leftarrow ?</tex>?
[[Участник:Shevchen|Дмитрий Шевченко]] 17:52, 4 июня 2012 (GST)
: Какая угодно, но конечная. Она ограничена размером машины Тьюринга. Это же как бы недетерминированный переход. Сколько в машине переходов есть, такая и мощность. С поправкой на то, правда, что тут программа, а не машина, и один такой оператор может скрывать в себе несколько переходов аналогичной машины.