Участник:Shersh/Тикеты к 6ому терму — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎1. Детерминированные и недетерминированные вычисления, сложность по времени и по памяти)
(→‎2. Классы P и NP, NP-полнота)
Строка 17: Строка 17:
  
 
=== 2. Классы P и NP, NP-полнота ===
 
=== 2. Классы P и NP, NP-полнота ===
−
*[[Класс P]]
+
# [[Класс P]] (3)
−
*[[Недетерминированные вычисления]]
+
## Отформатировать по правилам
−
*[[Классы NP и Σ₁]]
+
# [[Недетерминированные вычисления]] (2)
−
*[[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи]]
+
## Отформатировать по правилам
−
*[[NP-полнота BH1N]]
+
## Какую-нибудь разумную структура конспекта создать
−
*[[Теорема Кука]]
+
## Добавить примеров
−
*[[Теоремы о временной и емкостной иерархиях]]
+
# '''!!!''' [[Классы NP и Σ₁]] (7)
−
*[[Теорема Бейкера — Гилла — Соловэя]]
+
## Отформатировать по правилам
−
*[[Теорема Ладнера]]
+
## Доказать для некоторых языков из примеров, что они в NP
−
*[[Теорема Левина]]
+
## Ещё простых примеров с доказательством
−
*[[Теорема Бермана — Форчуна]]
+
## Добавить определение coNP, примеры языков по возможности с доказательствами
−
*[[Теорема Махэни]]
+
# [[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи]] (1.5-2)
 +
## Отформатировать по правилам
 +
## Возможно добавить ещё более просто пример
 +
# [[NP-полнота BH1N]] (1)
 +
## Отформатировать по правилам
 +
# [[Теорема Кука]] (2)
 +
## Отформатировать по правилам
 +
## Сделать табличку красивой
 +
# [[Теоремы о временной и емкостной иерархиях]] (1)
 +
## Отформатировать по правилам
 +
# [[Теорема Бейкера — Гилла — Соловэя]] (3)
 +
## Отформатировать по правилам
 +
## Пояснить подробней все переходы
 +
# [[Теорема Ладнера]] (2)
 +
## Отформатировать по правилам
 +
# [[Теорема Левина]] (2)
 +
## Отформатировать по правилам
 +
## Пояснить неформальный смысл теоремы
 +
## Возможно подробней описать
 +
# [[Теорема Бермана — Форчуна]] (2)
 +
## Отформатировать по правилам
 +
## Добавить структуру конспекту
 +
# [[Теорема Махэни]] (3)
 +
## Отформатировать по правилам
 +
## Пояснить обозначения в начале
  
 
=== 3. [[Примеры NP-полных языков]] ===
 
=== 3. [[Примеры NP-полных языков]] ===

Версия 23:27, 24 февраля 2016

Тикеты подаются в формате X-Y-Z или X.Y.Z.

1. Детерминированные и недетерминированные вычисления, сложность по времени и по памяти

1. Базовые определения

  1. Сложностные классы (3)
    1. Убрать пункт История
    2. Прафильно раставить тех
    3. Сделать отсылку к теорию вычислимости
    4. Сформулировать определения в терминах МТ (смотри трешовую версию)
    5. Категории
    6. См. также, Источники информации
    7. Возможно добавить ещё чуть-чуть информации с википедии или откуда-нибудь
    8. Интервики
  2. Вычисления с оракулом (1)
    1. Добавить различные определения сведения, в том числе из трешовой версии
    2. Отформатировать по правилам

2. Классы P и NP, NP-полнота

  1. Класс P (3)
    1. Отформатировать по правилам
  2. Недетерминированные вычисления (2)
    1. Отформатировать по правилам
    2. Какую-нибудь разумную структура конспекта создать
    3. Добавить примеров
  3. !!! Классы NP и Σ₁ (7)
    1. Отформатировать по правилам
    2. Доказать для некоторых языков из примеров, что они в NP
    3. Ещё простых примеров с доказательством
    4. Добавить определение coNP, примеры языков по возможности с доказательствами
  4. Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи (1.5-2)
    1. Отформатировать по правилам
    2. Возможно добавить ещё более просто пример
  5. NP-полнота BH1N (1)
    1. Отформатировать по правилам
  6. Теорема Кука (2)
    1. Отформатировать по правилам
    2. Сделать табличку красивой
  7. Теоремы о временной и емкостной иерархиях (1)
    1. Отформатировать по правилам
  8. Теорема Бейкера — Гилла — Соловэя (3)
    1. Отформатировать по правилам
    2. Пояснить подробней все переходы
  9. Теорема Ладнера (2)
    1. Отформатировать по правилам
  10. Теорема Левина (2)
    1. Отформатировать по правилам
    2. Пояснить неформальный смысл теоремы
    3. Возможно подробней описать
  11. Теорема Бермана — Форчуна (2)
    1. Отформатировать по правилам
    2. Добавить структуру конспекту
  12. Теорема Махэни (3)
    1. Отформатировать по правилам
    2. Пояснить обозначения в начале

3. Примеры NP-полных языков

4. Сложность по памяти, классы PS, L, NL, coNL

5. Полиномиальная иерархия

2. Схемная сложность

3. Вероятностные сложностные классы

1. Основные классы

2. Интерактивные протоколы

3. Probabilistically checkable proofs

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Участник:Shersh/Тикеты_к_6ому_терму&oldid=52200»