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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (→‎Вероятностные сложностные классы)
м (Изменён уровень защиты страницы «Участник:Shersh/Тикеты к 6ому терму» ([edit=autoconfirmed] (бессрочно) [move=autoconfirmed] (бессрочно)))
 
(не показано 37 промежуточных версий 2 участников)
Строка 1: Строка 1:
−
== Детерминированные и недетерминированные вычисления, сложность по времени и по памяти ==
+
Тикеты подаются в формате X-Y-Z или X.Y.Z.
−
*[[Сложностные классы]]
 
−
*[[Вычисления с оракулом]]
 
  
−
=== Классы P и NP, NP-полнота ===
+
== 1. Детерминированные и недетерминированные вычисления, сложность по времени и по памяти ==
−
*[[Класс P]]
+
=== 1. Базовые определения ===
−
*[[Недетерминированные вычисления]]
+
# ''взяли'' [[Сложностные классы]] (3)
−
*[[Классы NP и Σ₁]]
+
## Убрать пункт История
−
*[[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи]]
+
## Прафильно раставить тех
−
*[[NP-полнота BH1N]]
+
## Сделать отсылку к теорию вычислимости
−
*[[Теорема Кука]]
+
## Сформулировать определения в терминах МТ (смотри трешовую версию)
−
*[[Примеры NP-полных языков]]
+
## Категории
−
*[[Теоремы о временной и емкостной иерархиях]]
+
## См. также, Источники информации
−
*[[Теорема Бейкера — Гилла — Соловэя]]
+
## Возможно добавить ещё чуть-чуть информации с википедии или откуда-нибудь
−
*[[Теорема Ладнера]]
+
## Интервики
−
*[[Теорема Левина]]
+
# [[Вычисления с оракулом]] (1)
−
*[[Теорема Бермана — Форчуна]]
+
## Добавить различные определения сведения, в том числе из трешовой версии
−
*[[Теорема Махэни]]
+
## Отформатировать по правилам
  
−
=== Сложность по памяти, классы PS, L, NL, coNL ===
+
=== 2. Классы P и NP, NP-полнота ===
−
*[[Класс PS. Связь класса PS с другими классами теории сложности]]
+
# [[Класс P]] (3)
−
*[[Теорема Сэвича. Совпадение классов NPS и PS]]
+
## Отформатировать по правилам
−
*[[PS-полнота языка верных булевых формул с кванторами (TQBF)]]
+
## Добавить про тильду
−
*[[Классы L, NL, coNL]]
+
# ''взяли'' [[Недетерминированные вычисления]] (2)
−
*[[Полнота относительно L-сведения. NL-полнота. P-полнота]]
+
## Отформатировать по правилам
−
*[[Теорема Иммермана]]
+
## Какую-нибудь разумную структура конспекта создать
 +
## Добавить примеров
 +
# '''fixed''' [[Классы NP и Σ₁]] (7)
 +
## Отформатировать по правилам
 +
## Доказать для некоторых языков из примеров, что они в NP
 +
## Ещё простых примеров с доказательством
 +
## Добавить определение coNP, примеры языков по возможности с доказательствами
 +
# [[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи]] (1.5-2)
 +
## Отформатировать по правилам
 +
## Возможно добавить ещё более простой пример
 +
# ''fixed'' [[NP-полнота BH1N]] (1)
 +
## Отформатировать по правилам
 +
# ''взяли'' [[Теорема Кука]] (2)
 +
## Отформатировать по правилам
 +
## Сделать табличку красивой
 +
# [[Теоремы о временной и емкостной иерархиях]] (1)
 +
## Отформатировать по правилам
 +
# [[Теорема Бейкера — Гилла — Соловэя]] (4)
 +
## Отформатировать по правилам
 +
## Пояснить подробней все переходы
 +
## Пояснить подробней последнюю теорему, дать ссылки примечаниями
 +
# [[Теорема Ладнера]] (2)
 +
## Отформатировать по правилам
 +
# [[Теорема Левина]] (2)
 +
## Отформатировать по правилам
 +
## Пояснить неформальный смысл теоремы
 +
## Возможно подробней описать
 +
# [[Теорема Бермана — Форчуна]] (2)
 +
## Отформатировать по правилам
 +
## Добавить структуру конспекту
 +
# ''fixed'' [[Теорема Махэни]] (4)
 +
## Отформатировать по правилам
 +
## Пояснить обозначения в начале
 +
## Добавить, что такое SPARSE: [[Редкие языки]]
  
−
=== Полиномиальная иерархия ===
+
=== 3. [[Примеры NP-полных языков]] ===
−
*[[Классы PH, Σ и Π]]
+
# [[NP-полнота языка CNFSAT]] (1)
−
*[[Теоремы о коллапсе полиномиальной иерархии]]
+
## Выпилить из большого конспекта, а в нём сделать ссылку как на основную статью
 +
## Оформить правильно
 +
# [[NP-полнота языка 3SAT]] (1)
 +
## Выпилить из большого конспекта, а в нём сделать ссылку как на основную статью
 +
## Оформить правильно
 +
# [[NP-полнота языка IND (максимальное независимое множество)]] (3)
 +
## Выпилить из большого конспекта, а в нём сделать ссылку как на основную статью
 +
## Оформить правильно
 +
## Добавить картинку графа-примера
 +
# [[NP-полнота языка VCOVER (минимальное вершинное покрытие)]] (1)
 +
## Выпилить из большого конспекта, а в нём сделать ссылку как на основную статью
 +
## Оформить правильно
 +
# [[NP-полнота языка FACTOR]] (3)
 +
## Оформить правильно
 +
## Пояснить происходящее
 +
# [[NP-полнота языка CLIQUE]] (2)
 +
## Оформить правильно
 +
## Проинлайнить доказательство
 +
# '''fixed''' [[NP-полнота задач о гамильтоновом цикле и пути в графах]] (5)
 +
## Оформить правильно
 +
## Картинки сделать красивыми
 +
# ''fixed'' [[NP-полнота задачи о сумме подмножества]] (3)
 +
## Оформить правильно
 +
# [[NP-полнота задачи о рюкзаке]] (3)
 +
## Оформить правильно
 +
## Пояснить подробней
 +
# [[NP-полнота задачи о раскраске графа]] (2)
 +
## Оформить правильно
  
−
== Схемная сложность ==
+
=== 4. Сложность по памяти, классы PS, L, NL, coNL, EXP, NEXP ===
−
*[[Схемная сложность и класс P/poly]]
+
#[[Класс PS. Связь класса PS с другими классами теории сложности]] (1)
−
*[[Теорема Карпа — Липтона]]
+
## Отформатировать по правилам
−
*[[Классы NC и AC]]
+
## Как-то помёрджить с [[Класс PS]]
−
*[[Теорема о непринадлежности XOR классу AC⁰]]
+
#[[Теорема Сэвича. Совпадение классов NPS и PS]] (1)
 +
## Отформатировать по правилам
 +
#[[PS-полнота языка верных булевых формул с кванторами (TQBF)]] (1)
 +
## Отформатировать по правилам
 +
# [[PS-полнота задачи Generalized geography]] (4)
 +
## Отформатировать по правилам
 +
## Привести примеры, где может быть актуально решать такую задачу
 +
#[[Классы L, NL, coNL]] (3)
 +
## Отформатировать по правилам
 +
## Добавить больше неформальных пояснений к классам
 +
## Добавить ещё несколько утверждений про связи классов L с другими
 +
## Помёрджить с этим конспектом и другими из треша: [[NL-полнота]]
 +
#[[Полнота относительно L-сведения. NL-полнота. P-полнота]] (2)
 +
## Отформатировать по правилам
 +
#[[Теорема Иммермана]] (2)
 +
## Отформатировать по правилам
 +
# [[Классы EXP и NEXP]] (4)
 +
## Смёрджить два конспекта и отформатировать по правилам: [[Классы EXP, NEXP. Полнота языков EXP и NEXP]], [[Теорема о связи вопросов EXP=NEXP и P=NP]]
  
−
== Вероятностные сложностные классы ==
+
=== 5. Полиномиальная иерархия ===
−
=== Основные классы ===
+
#[[Классы PH, Σ и Π]] (3)
−
*[[Вероятностные вычисления. Вероятностная машина Тьюринга]]
+
## Отформатировать по правилам
−
*[[Классы RP и coRP]]
+
## Доказать простенькие отношений отсюда: [[Классы Sigma i и Pi i]], [[Полиномиальная иерархия]]
−
*[[Класс ZPP]]
+
#[[Теоремы о коллапсе полиномиальной иерархии]] (2)
−
*[[Классы BPP и PP]]
+
## Отформатировать по правилам
−
*[[Соотношение вероятностных классов]]
 
−
*[[Теорема Лаутемана]]
 
  
−
=== Интерактивные протоколы ===
+
== 2. Схемная сложность ==
−
*[[Интерактивные протоколы. Класс IP. Класс AM]]
+
#[[Схемная сложность и класс P/poly]] (1)
−
*[[Арифметизация булевых формул с кванторами]]
+
## Отформатировать по правилам
−
*[[Теорема о соотношении coNP и IP]]
+
#[[Теорема Карпа — Липтона]] (2)
−
*[[Теорема Шамира]]
+
## Отформатировать по правилам
−
*[[Семейство универсальных попарно независимых хеш-функций]]
+
## Помёрджить с [[Теорема Карпа-Липтона]] (0.5)
−
*[[Протокол Голдвассер-Сипсера для оценки размера множества]]
+
#[[Классы NC и AC]]
 +
## Добавить Источники информации и См. также
 +
#[[Теорема о непринадлежности XOR классу AC⁰]] (2)
 +
## Оформить по правилам
  
−
=== Probabilistically checkable proofs ===
+
== 3. Вероятностные сложностные классы ==
−
*[[PCP-система]]
+
=== 1. Основные классы ===
−
*[[Эквивалентность PCP-теоремы и теоремы о трудности аппроксимации]]
+
#[[Вероятностные вычисления. Вероятностная машина Тьюринга]] (2)
−
*[[PCP-теорема]]
+
## Отформатировать по правилам
 +
## Помёрджить с [[Вероятностная машина Тьюринга]]
 +
#[[Классы RP и coRP]] (3)
 +
## Отформатировать по правилам
 +
## Помёрджить с [[Сложностные классы RP и coRP]] и [[Уменьшение ошибки в классе RP, сильное и слабое определение]]
 +
#[[Класс ZPP]] (2)
 +
## Отформатировать по правилам
 +
## Помёрджить с [[Сложностный класс ZPP]]
 +
#[[Классы BPP и PP]] (3)
 +
## Отформатировать по правилам
 +
## Помёрджить с [[Сложностный класс PP]] и [[Сложностный класс BPP]]
 +
#[[Соотношение вероятностных классов]] (2)
 +
## Отформатировать по правилам
 +
## Добавить сюда [[Теорема о включении BPP в P/poly]]
 +
#[[Лемма Шварца-Зиппеля]] (3)
 +
## Отформатировать по правилам
 +
#[[Теорема Лаутемана]] (1)
 +
## Отформатировать по правилам
 +
#[[Теорема Валианта-Вазирани]] (3)
 +
## Отформатировать по правилам
 +
 
 +
=== 2. Интерактивные протоколы ===
 +
# ''fixed'' [[Интерактивные протоколы. Класс IP. Класс AM]] (4)
 +
## Отформатировать по правилам
 +
## Увеличить картинку
 +
## Написать больше неформальных пояснений
 +
## +1 за более красивую векторную картинку
 +
# [[Арифметизация булевых формул с кванторами]] (4)
 +
## Отформатировать по правилам
 +
## Добавить структуру конспекту
 +
## Написать непонятные места понятней
 +
# ''fixed'' [[Теорема о соотношении coNP и IP]] (4)
 +
## Отформатировать по правилам
 +
## Написать непонятные места понятней
 +
# [[Теорема Шамира]] (3)
 +
## Отформатировать по правилам
 +
# '''взяли''' [[Семейство универсальных попарно независимых хеш-функций]] (5)
 +
## Отформатировать по правилам
 +
## Интервики на конспекты хеширования, там уже что-то есть про универсальное семейство
 +
# '''!!!''' [[Протокол Голдвассер-Сипсера для оценки размера множества]] (7)
 +
## Написать понятно
 +
## Отформатировать по правилам
 +
## Переименовать конспект
 +
## Добавить [[Теорема Голдвассера, Сипсера | теорему]] (+3 за правильное доказательство)
 +
 
 +
=== 3. Probabilistically checkable proofs ===
 +
# [[PCP-система]] (3)
 +
## Отформатировать по правилам
 +
# [[Эквивалентность PCP-теоремы и теоремы о трудности аппроксимации]] (4)
 +
## Отформатировать по правилам
 +
## Написать понятней
 +
## Пояснить, что даёт эта эквивалентность
 +
# '''!!!''' [[PCP-теорема]] (10)
 +
## Сделать всё хорошо

Текущая версия на 19:15, 23 февраля 2017

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

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

  1. NP-полнота языка CNFSAT (1)
    1. Выпилить из большого конспекта, а в нём сделать ссылку как на основную статью
    2. Оформить правильно
  2. NP-полнота языка 3SAT (1)
    1. Выпилить из большого конспекта, а в нём сделать ссылку как на основную статью
    2. Оформить правильно
  3. NP-полнота языка IND (максимальное независимое множество) (3)
    1. Выпилить из большого конспекта, а в нём сделать ссылку как на основную статью
    2. Оформить правильно
    3. Добавить картинку графа-примера
  4. NP-полнота языка VCOVER (минимальное вершинное покрытие) (1)
    1. Выпилить из большого конспекта, а в нём сделать ссылку как на основную статью
    2. Оформить правильно
  5. NP-полнота языка FACTOR (3)
    1. Оформить правильно
    2. Пояснить происходящее
  6. NP-полнота языка CLIQUE (2)
    1. Оформить правильно
    2. Проинлайнить доказательство
  7. fixed NP-полнота задач о гамильтоновом цикле и пути в графах (5)
    1. Оформить правильно
    2. Картинки сделать красивыми
  8. fixed NP-полнота задачи о сумме подмножества (3)
    1. Оформить правильно
  9. NP-полнота задачи о рюкзаке (3)
    1. Оформить правильно
    2. Пояснить подробней
  10. NP-полнота задачи о раскраске графа (2)
    1. Оформить правильно

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

  1. Класс PS. Связь класса PS с другими классами теории сложности (1)
    1. Отформатировать по правилам
    2. Как-то помёрджить с Класс PS
  2. Теорема Сэвича. Совпадение классов NPS и PS (1)
    1. Отформатировать по правилам
  3. PS-полнота языка верных булевых формул с кванторами (TQBF) (1)
    1. Отформатировать по правилам
  4. PS-полнота задачи Generalized geography (4)
    1. Отформатировать по правилам
    2. Привести примеры, где может быть актуально решать такую задачу
  5. Классы L, NL, coNL (3)
    1. Отформатировать по правилам
    2. Добавить больше неформальных пояснений к классам
    3. Добавить ещё несколько утверждений про связи классов L с другими
    4. Помёрджить с этим конспектом и другими из треша: NL-полнота
  6. Полнота относительно L-сведения. NL-полнота. P-полнота (2)
    1. Отформатировать по правилам
  7. Теорема Иммермана (2)
    1. Отформатировать по правилам
  8. Классы EXP и NEXP (4)
    1. Смёрджить два конспекта и отформатировать по правилам: Классы EXP, NEXP. Полнота языков EXP и NEXP, Теорема о связи вопросов EXP=NEXP и P=NP

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

  1. Классы PH, Σ и Π (3)
    1. Отформатировать по правилам
    2. Доказать простенькие отношений отсюда: Классы Sigma i и Pi i, Полиномиальная иерархия
  2. Теоремы о коллапсе полиномиальной иерархии (2)
    1. Отформатировать по правилам

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

  1. Схемная сложность и класс P/poly (1)
    1. Отформатировать по правилам
  2. Теорема Карпа — Липтона (2)
    1. Отформатировать по правилам
    2. Помёрджить с Теорема Карпа-Липтона (0.5)
  3. Классы NC и AC
    1. Добавить Источники информации и См. также
  4. Теорема о непринадлежности XOR классу AC⁰ (2)
    1. Оформить по правилам

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

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

  1. Вероятностные вычисления. Вероятностная машина Тьюринга (2)
    1. Отформатировать по правилам
    2. Помёрджить с Вероятностная машина Тьюринга
  2. Классы RP и coRP (3)
    1. Отформатировать по правилам
    2. Помёрджить с Сложностные классы RP и coRP и Уменьшение ошибки в классе RP, сильное и слабое определение
  3. Класс ZPP (2)
    1. Отформатировать по правилам
    2. Помёрджить с Сложностный класс ZPP
  4. Классы BPP и PP (3)
    1. Отформатировать по правилам
    2. Помёрджить с Сложностный класс PP и Сложностный класс BPP
  5. Соотношение вероятностных классов (2)
    1. Отформатировать по правилам
    2. Добавить сюда Теорема о включении BPP в P/poly
  6. Лемма Шварца-Зиппеля (3)
    1. Отформатировать по правилам
  7. Теорема Лаутемана (1)
    1. Отформатировать по правилам
  8. Теорема Валианта-Вазирани (3)
    1. Отформатировать по правилам

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

  1. fixed Интерактивные протоколы. Класс IP. Класс AM (4)
    1. Отформатировать по правилам
    2. Увеличить картинку
    3. Написать больше неформальных пояснений
    4. +1 за более красивую векторную картинку
  2. Арифметизация булевых формул с кванторами (4)
    1. Отформатировать по правилам
    2. Добавить структуру конспекту
    3. Написать непонятные места понятней
  3. fixed Теорема о соотношении coNP и IP (4)
    1. Отформатировать по правилам
    2. Написать непонятные места понятней
  4. Теорема Шамира (3)
    1. Отформатировать по правилам
  5. взяли Семейство универсальных попарно независимых хеш-функций (5)
    1. Отформатировать по правилам
    2. Интервики на конспекты хеширования, там уже что-то есть про универсальное семейство
  6. !!! Протокол Голдвассер-Сипсера для оценки размера множества (7)
    1. Написать понятно
    2. Отформатировать по правилам
    3. Переименовать конспект
    4. Добавить теорему (+3 за правильное доказательство)

3. Probabilistically checkable proofs

  1. PCP-система (3)
    1. Отформатировать по правилам
  2. Эквивалентность PCP-теоремы и теоремы о трудности аппроксимации (4)
    1. Отформатировать по правилам
    2. Написать понятней
    3. Пояснить, что даёт эта эквивалентность
  3. !!! PCP-теорема (10)
    1. Сделать всё хорошо
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Участник:Shersh/Тикеты_к_6ому_терму&oldid=60460»