Темы

Сложность вычислений

Computational Complexity · 88 статей

  1. Класс сложности BPP: Вероятностные алгоритмы полиномиального времени

    BPP в теории сложности: класс задач, решаемых вероятностными алгоритмами за полиномиальное время с ошибкой ≤1/3. Включает класс P. Эффективные алгоритмы!

    #862 · 6 мин чтения

  2. Класс сложности BQP: квантовый полиномиальный алгоритм с ограниченной ошибкой.

    BQP: класс задач, решаемых квантовым компьютером за полиномиальное время с малой вероятностью ошибки (≤1/3). Квантовый аналог BPP. Теория вычислительной сложности.

    #863 · 3 мин чтения

  3. Проблема выполнимости булевых формул

    Проблема выполнимости булевых формул (SAT): определение, можно ли присвоить переменным значения ИСТИНА/ЛОЖЬ, чтобы формула стала истинной. Логика, компьютерные науки.

    #1022 · 12 мин чтения

  4. Сложность алгоритмов и вычислительная сложность

    Вычислительная сложность алгоритмов: время работы и потребление памяти. Анализ алгоритмов и теория вычислительной сложности – ключевые понятия в CS.

    #1434 · 11 мин чтения

  5. Сложность вычислений: теоретические основы и границы решаемости.

    Теория вычислительной сложности: классификация задач по ресурсам, необходимым для решения. Изучение трудностей алгоритмов и математических вычислений.

    #1693 · 22 мин чтения

  6. Проблемы принятия решений в теории вычислимости и сложности

    Проблемы принятия решений в информатике: что такое, примеры (проверка числа на простоту, делимость). Алгоритмы и процедуры решения yes/no задач.

    #1905 · 5 мин чтения

  7. Класс сложности NP: определение и свойства.

    Класс NP в теории сложности вычислений: задачи, решения которых можно проверить за полиномиальное время. Определение, свойства и применение NP.

    #5200 · 3 мин чтения

  8. Недетерминированная машина Тьюринга: Теоретическая модель вычислений

    Недетерминированная машина Тьюринга: теоретическая модель вычислений в компьютерной науке. Исследование P vs NP, возможностей и ограничений компьютеров.

    #5275 · 4 мин чтения

  9. Класс сложности NC: параллельные вычисления и полилогарифмическая сложность.

    Класс NC в теории сложности вычислений: задачи, решаемые за полилогарифмическое время на параллельном компьютере. Эффективные параллельные алгоритмы, подкласс P.

    #5302 · 6 мин чтения

  10. Оракульная машина: абстрактная модель для изучения вычислительных задач.

    Машина Оракула: абстрактная вычислительная модель для изучения решаемости задач. Используется в теории вычислимости и сложности, как Тьюринг-машина с "черным ящиком".

    #5365 · 5 мин чтения

  11. Класс сложности #P

    класс сложности: подсчет решений задач из NP. Определение, связь с NP-полными задачами, функции вместо решений. Теория вычислительной сложности.

    #6780 · 2 мин чтения

  12. #P-полные задачи: теория и приложения

    -полные задачи в теории вычислительной сложности: определение, свойства (,-трудность), счетные и Turing-редукции. Оптимизация алгоритмов.

    #6781 · 2 мин чтения

  13. Стивен Кук и проблема P vs. NP: Основы теории сложности вычислений

    Стивен Кук: вклад в теорию сложности, NP-полнота, теорема Кука-Левина и формулировка P vs NP. Основы современной информатики и алгоритмов.

    #9277 · 3 мин чтения

  14. Полнота по co-NP: Теория и примеры

    co-NP полные задачи: самые сложные в co-NP. Если P≠co-NP, то не решаются за полиномиальное время. Связь с NP-полными задачами и алгоритмами.

    #12803 · 2 мин чтения

  15. Сложность вычислений: более простое введение.

    NP-трудные задачи в теории сложности вычислений: определение, полиномиальное сведение, связь с классом NP и гипотезой P≠NP. Пример: задача о сумме подмножества.

    #12804 · 2 мин чтения

  16. P-полные задачи: параллелизация и сложность пространства

    P-полные задачи в теории сложности вычислений: определение, важность для анализа параллелизма и ограниченной памяти. Редукции и их типы.

    #12805 · 3 мин чтения

  17. Полнота по пространству PSPACE: обзор и свойства

    ПСАПРО-полнота: самые сложные задачи, решаемые за полиномиальное пространство. Свойства регулярных выражений, игры, граммы и др. Теория вычислительной сложности.

    #12806 · 4 мин чтения

  18. NP-Эквивалентные задачи и их свойства

    NP-эквивалентные задачи в теории сложности: определение, пример (FIND SUBSET SUM). Оптимизационные проблемы, аналоги NP-полноты для функциональных задач.

    #12807 · 2 мин чтения

  19. Класс сложности EXPTIME: определение и свойства

    EXPTIME: класс сложности задач, решаемых детерминированной машиной Тьюринга за экспоненциальное время (O(2p(n))). Связь с P, NP, PSPACE и другими классами.

    #12809 · 3 мин чтения

  20. EXPSPACE-полные задачи и вычислительная сложность

    Проблемы в теории сложности вычислений: класс EXP, экспоненциальное пространство, полнота по многократному полиномиальному времени, примеры и соотношения с другими классами.

    #12811 · 2 мин чтения

  21. Случайные алгоритмы полиномиального времени (RP)

    Сложность RP в теории вычислимости: вероятностные алгоритмы, полиномиальное время, вероятность ответа "да" ≥ 1/2. Определение, свойства, отличия от R.

    #12822 · 3 мин чтения

  22. ZPP: Класс сложности с нулевой вероятностью ошибки

    ZPP в теории сложности: полиномиальное время работы вероятностной машины Тьюринга с нулевой ошибкой. Алгоритмы Лас-Вегаса, корректный ответ всегда.

    #12823 · 3 мин чтения

  23. Алгоритм Гровера: квантовый поиск в квадратичном ускорении

    Алгоритм Гровера: квантовый поиск в базах данных. Обеспечивает квадратичное ускорение по сравнению с классическими алгоритмами, оптимален для поиска по чёрному ящику.

    #13662 · 5 мин чтения

  24. Дизъюнктивная нормальная форма булевой функции

    ДНФ (дизъюнктивная нормальная форма) в булевой логике: канонический вид логических формул, преобразование с помощью логических эквивалентностей. Автоматическое доказательство теорем.

    #16761 · 1 мин чтения

  25. Сопряжённая нормальная форма булевых функций

    Нормальная конъюнктивная форма (CNF) в булевой логике: определение, преобразование формул, применение в автоматическом доказательстве теорем и схемотехнике.

    #16762 · 2 мин чтения

  26. Полиномиальное сведение в теории сложности вычислений

    Полиномиальное сведение в теории сложности: решение задач через другие задачи. Доказательство, что одна задача не сложнее другой. Оптимизация алгоритмов.

    #49674 · 4 мин чтения

  27. Интерактивные доказательные системы в теории сложности вычислений

    Интерактивные доказательства: теория сложности вычислений, протоколы верификации, честный верификатор и ненадежный доказывающий. Полнота доказательства.

    #49789 · 9 мин чтения

  28. Теорема об иерархии времени для машин Тьюринга

    Теоремы о временной иерархии Тьюринга: больше времени – больше решаемых задач. Доказательство Стеарнса и Хартманиса (1965), усовершенствовано Хенни и Стеарнсом.

    #55221 · 3 мин чтения

  29. Вероятностная машина Тьюринга и сложность вычислений

    Вероятностная машина Тьюринга: модель вычислений с случайными переходами. Различия от детерминированных машин, вероятностные результаты, квантовые вычисления.

    #57756 · 3 мин чтения

  30. Задачи удовлетворения ограничений: обзор и методы решения

    Задачи удовлетворения ограничений (CSPs): математические модели поиска решений при заданных условиях. ИИ, исследования операций, constraint programming.

    #60309 · 7 мин чтения

  31. Сложность алгоритмов по памяти

    Сложность памяти алгоритма: объём используемой памяти для решения задачи. Влияние размера входных данных, Big O нотация, LOGSPACE. Оптимизация памяти.

    #81768 · 1 мин чтения

  32. Многооднозначные редукции в теории вычислимости

    Многооднозначные редукции в теории вычислимости: преобразование задач с помощью вычислимой функции для оценки сложности. m-полные множества и сильная приводимость.

    #85731 · 2 мин чтения

  33. Односторонние функции в компьютерной криптографии

    Односторонние функции в криптографии: легко вычислить, сложно инвертировать. Важны для безопасности, существование – открытый вопрос в теории сложности.

    #85871 · 4 мин чтения

  34. 2-Удовлетворимость: Полиномиальная разрешимость и приложения

    2-SAT: решение задач выполнимости булевых формул с двумя литералами в каждом дизъюнкте. Полиномиальный алгоритм, графы импликаций, 2CNF формулы.

    #108089 · 20 мин чтения

  35. Классы сложности в теории вычислимости

    Классы сложности в теории вычислимости: определение, ресурсы (время, память), модели вычислений и пример класса P. Изучение вычислительных задач.

    #108738 · 29 мин чтения

  36. Проверочные доказательства с вероятностью: теория и применение.

    Доказательства с вероятностной проверкой (PCP) в теории сложности: проверка доказательств рандомизированным алгоритмом с малым объемом чтения. Классы сложности.

    #109155 · 2 мин чтения

  37. Алгоритмы Лас-Вегаса: характеристики и анализ времени работы

    Алгоритмы Лас-Вегаса: рандомизированные алгоритмы, всегда дающие верный результат или сообщающие об ошибке. Подходят для задач с ограниченным числом решений.

    #113738 · 4 мин чтения

  38. Двоичные решающие диаграммы: структура данных для булевых функций

    Бинарные диаграммы решений (BDD): структура данных для представления булевых функций. Сжатое кодирование, операции без декомпрессии. Компьютерные науки.

    #118929 · 2 мин чтения

  39. Параметризованная сложность: теория и применение.

    Параметризованная сложность: классификация вычислительных задач по параметрам. Решение NP-трудных задач возможно за полиномиальное время при малых параметрах k.

    #122547 · 7 мин чтения

  40. Пространственная сложность и DSPACE в теории вычислимости

    Пространственная сложность DSPACE: определение, роль в теории вычислимости, измерение памяти детерминированной машины Тьюринга. Классы сложности.

    #130657 · 1 мин чтения

  41. Временная сложность в теории вычислительной сложности

    Временная сложность DTIME в теории вычислительной сложности: определение, значение для детерминированных машин Тьюринга и классов задач. Оптимизация алгоритмов.

    #130659 · 3 мин чтения

  42. Класс сложности P и полиномиальная сложность

    Класс P в теории сложности вычислений: задачи, решаемые за полиномиальное время. Эффективные алгоритмы, детерминированные машины Тьюринга, линейное программирование.

    #130661 · 5 мин чтения

  43. Полиномиальная иерархия в теории вычислительной сложности

    Полиномиальная иерархия в теории сложности вычислений: обобщение классов NP и co NP, определение через оракулы и машины Тьюринга. PH – объединение классов.

    #130679 · 4 мин чтения

  44. Класс сложности PP: Вероятностные алгоритмы и полиномиальное время

    PP в теории сложности: задачи, решаемые вероятностной машиной Тьюринга за полиномиальное время с вероятностью ошибки <1/2. Определение и алгоритмы.

    #130765 · 6 мин чтения

  45. Ускорение машин Тьюринга за счёт увеличения сложности символов ленты.

    Ускорение машин Тьюринга: линейное увеличение скорости вычислений за счет повышения сложности символов на ленте. Теория вычислительной сложности.

    #131216 · 1 мин чтения

  46. Теорема Кука — Левина и NP-полнота задач

    Теорема Кука-Левина: доказывает NP-полноту задачи выполнимости булевых формул (SAT). Основа теории вычислительной сложности, NP-полные задачи.

    #131221 · 4 мин чтения

  47. Теоремы о пространственной иерархии в теории вычислительной сложности

    Теоремы об иерархии пространства в теории вычислительной сложности: чем больше памяти, тем больше решаемых задач. Доказательство и применение.

    #131223 · 4 мин чтения

  48. Интерактивные доказательства и классы сложности AM и MA

    Интерактивные доказательства Arthur-Merlin: протокол в теории вычислительной сложности. Верификация с публичными случайными числами, проверка честности доказуемости.

    #131255 · 4 мин чтения

  49. Функциональные задачи в теории вычислительной сложности

    Функциональные задачи в теории сложности вычислений: поиск не просто "да/нет", а сложных выходных данных. Пример – FSAT, связанный с SAT.

    #131270 · 3 мин чтения

  50. Класс сложности FNP: определение и свойства.

    FNP класс сложности в теории вычислимости: бинарные отношения, проверяемые за полиномиальное время. Связь с классом NP и задачами принятия решений.

    #131271 · 2 мин чтения

  51. Класс сложности NEXPTIME: определения и характеристики.

    NEXPTIME: класс сложности задач, решаемых недетерминированной машиной Тьюринга за экспоненциальное время. Определение, теоремы, связь с NP и логикой.

    #131315 · 3 мин чтения

  52. Чередующаяся машина Тьюринга: Модель вычислений и классы сложности.

    Альтернативная машина Тьюринга (ATM): модель вычислений в теории сложности. Объединяет NP и co-NP, чередуя режимы существования и универсальности.

    #141603 · 3 мин чтения

  53. Класс сложности NL: определение и свойства.

    NL в теории сложности: недетерминированные алгоритмы, логарифмическая память. Определение, связь с классами L и NSPACE. Важные результаты и ресурсы.

    #186797 · 5 мин чтения

  54. Класс сложности L (логарифмическое пространство)

    Класс сложности L: детерминированные машины Тьюринга, логарифмическое пространство. USTCON в L = SL. Характеризация языков первого порядка с транзитивным замыканием.

    #187232 · 2 мин чтения

  55. Сложность SL: Равенство L и связь с задачей связности графа.

    Сложность SL в теории вычислительной сложности: задачи, сводимые к задаче связности USTCON в графах. Определение, связь с NL и STCON.

    #189946 · 5 мин чтения

  56. Случайный логарифмический класс (RL) в теории сложности вычислений

    RL-класс сложности: задачи, решаемые вероятностными машинами Тьюринга за полиномиальное время и логарифмическое пространство с односторонней ошибкой. Теория сложности.

    #190124 · 2 мин чтения

  57. Описательная сложность: логика и вычислительная сложность.

    Сложность описания: раздел математической логики, связывающий сложность вычислений и логику. Классы сложности и языки, выразимые логикой.

    #194118 · 7 мин чтения

  58. Удовлетворимость формул Хорна и полиномиальная разрешимость

    Удовлетворимость Horn (HORNSAT) в формальной логике: определение, свойства Horn-клауз и формул. P-полная задача, вычислимая за полиномиальное время.

    #196185 · 1 мин чтения

  59. Обещанные задачи в теории вычислительной сложности

    Обещающие задачи в теории сложности вычислений: обобщение задач принятия решений, где входные данные гарантированно принадлежат подмножеству.

    #220722 · 2 мин чтения

  60. Поисковые задачи в теории вычислимости и сложности

    Поиск в теории вычислимости: определение, связь с задачами принятия решений, обобщение на n-арные отношения и роль машины Тьюринга.

    #220764 · 1 мин чтения

  61. Преобразование к бинарным ограничениям в задачах удовлетворения ограничений

    Преобразование ограничений: упрощение задач поиска решений путем замены многоарных ограничений на бинарные. Сохранение решаемости и возможность применения эффективных алгоритмов.

    #250722 · 1 мин чтения

  62. Дополнение в теории вычислительной сложности

    Дополнение задачи в теории сложности вычислений: изменение ответов "да" и "нет". Пример – проверка на простоту vs. составное число. Определение и примеры.

    #265336 · 2 мин чтения

  63. Проблема изоморфизма графов: статус и современные достижения.

    Проблема изоморфизма графов: сложная задача в теории вычислительной сложности. Неизвестно, решается ли она за полиномиальное время. NP-промежуточная?

    #267177 · 6 мин чтения

  64. Проблемы, разрешимые малыми схемами (или P/poly)

    P/poly: класс задач, решаемых малыми схемами в теории сложности вычислений. Полиномиальное время, Turing-машины с подсказками, неuniform complexity.

    #276411 · 2 мин чтения

  65. Класс сложности ⊕P: определение и свойства.

    ⊕P: класс сложности задач, решаемых недетерминированной машиной Тьюринга за полиномиальное время с нечетным числом принимающих путей. ⊕SAT – ⊕P-полная задача.

    #282571 · 2 мин чтения

  66. Интерактивные доказательства и классы сложности IP, PSPACE, MIP

    IP-класс в теории сложности вычислений: интерактивные доказательства, равенство PSPACE. Работы Лунда, Шамира, Голдвассера, Микали и Раккоффа.

    #289677 · 3 мин чтения

  67. Программирование ответами: подход к сложным задачам поиска

    Программирование ответами (ASP): декларативный подход к сложным задачам поиска (NP-трудные). Решение через вычисление стабильных моделей, надежность и завершимость.

    #306614 · 4 мин чтения

  68. Алгоритм DPLL для решения задачи выполнимости булевых формул

    Алгоритм DPLL: полный метод решения задачи выполнимости булевых формул (CNF SAT). Основан на поиске с возвратом, разработан в 1961 году. Логика, компьютерные науки.

    #335464 · 2 мин чтения

  69. Сложность доказательств в логике и теории вычислимости.

    Сложность доказательств: изучение вычислительных ресурсов для доказательства теорем в логике и информатике. Границы длины доказательств, системы Фреге.

    #339041 · 7 мин чтения

  70. Immerman–Szelepcsényi theorem

    #341028 · 1 мин чтения

  71. ST-связность: сложность и полнота в классах сложности

    ST-связность в графах: определение, алгоритмы (DFS, BFS) и сложность в классах NL. Решение задачи о достижимости вершины t из s. Компьютерная наука.

    #341467 · 2 мин чтения

  72. Karp–Lipton theorem

    #343266 · 3 мин чтения

  73. Теорема Валианта — Вазирани: Если Unambiguous SAT решается за полиномиальное время, то NP = RP

    Теорема Валианта-Вазирани: если существует полиномиальный алгоритм для Unambiguous SAT, то NP=RP. Сложность NP-полных задач и уникальные решения.

    #354281 · 2 мин чтения

  74. Теорема Фагина: NP и экзистенциальная логика второго порядка

    Теорема Фагина: связь логики второго порядка и класса NP. Доказательство, история развития и значение в теории вычислительной сложности. Подробно о Fagin's theorem.

    #363178 · 2 мин чтения

  75. Псевдополиномиальное время и сложность NP-полных задач.

    Псевдополиномиальное время в теории сложности: алгоритмы, зависящие от числовых значений, а не длины ввода. Слабая и сильная NP-полнота.

    #365222 · 2 мин чтения

  76. Тезис Кобэма о вычислительной сложности и полиномиальном времени

    Тезис Кобэма: вычислимые задачи решаются за полиномиальное время (класс P). Определение сложности, трактабельность алгоритмов и ограничения теории вычислений.

    #373438 · 2 мин чтения

  77. Доказательства простоты и сертификаты простоты чисел

    Доказательство простоты: краткий, формальный способ подтвердить, что число простое, без сложных тестов. Важно для криптографии и теории вычислительной сложности.

    #400844 · 2 мин чтения

  78. Нулевое подавление в диаграммах принятия решений (ZSDD)

    Диаграмма принятия решений с подавлением нулей (ZSDD): компактное представление множеств для комбинаторных задач. Альтернативная нормальная форма для лучшей компрессии.

    #421483 · 5 мин чтения

  79. Двойственная задача в задачах об ограничениях: представление и графы двойственности.

    Двойственная задача в задачах на удовлетворение ограничений: упрощение решения с помощью бинарных ограничений, графов соединений и деревьев. Оптимизация!

    #422758 · 3 мин чтения

  80. Сложность задач удовлетворения ограничений: обзор и дихотомии

    Сложность задач удовлетворения ограничений: теория вычислительной сложности, NP-полнота, полиномиальные подслучаи, связь с базами данных и моделями.

    #445737 · 10 мин чтения

  81. Вычислительные задачи в теоретической информатике

    Вычислительные задачи в теории информатики: определение, примеры (факторизация чисел), сложность и неразрешимость. Изучение алгоритмов и ресурсов.

    #451441 · 3 мин чтения

  82. Полные задачи класса NL в теории сложности вычислений

    NL-полные задачи в теории сложности: определение, свойства и связь с классами L и NL. Недетерминированные машины Тьюринга, логарифмическая память.

    #451462 · 3 мин чтения

  83. Вычислительные ресурсы в теории сложности вычислений

    Вычислительные ресурсы: время, память и др. – ключевые факторы сложности решения задач в теории вычислений. Анализ ресурсов для эффективных алгоритмов.

    #453154 · 1 мин чтения

  84. Дихотомия Шефера и сложность задач выполнимости ограничений.

    Теорема Шефера о сложности булевых формул: условия, при которых задача решается за полиномиальное время или является NP-полной. Комплексность, SAT, CSP.

    #453677 · 2 мин чтения

  85. Классы сложности TFNP и PPAD в теории вычислительной сложности

    TFNP класс сложности в теории вычислимости: задачи с гарантированным решением, проверяемым за полиномиальное время. Факторизация, равновесие Нэша и др.

    #455167 · 4 мин чтения

  86. Полиномиальный локальный поиск (PLS) в теории сложности вычислений

    Полиномиальный локальный поиск (PLS): класс сложности задач оптимизации. Быстрая проверка локального оптимума, полиномиальное время решения и поиска.

    #455195 · 1 мин чтения

  87. PostBQP

    #461147 · 5 мин чтения

  88. Satisfiability modulo theories

    #477261 · 8 мин чтения