Сложностные классы — различия между версиями
м (rollbackEdits.php mass rollback) |
|||
Строка 1: | Строка 1: | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
В начале 1960-х годов, в связи с началом широкого использования вычислительной техники для решения практических задач, возник вопрос о границах практической применимости данного алгоритма решения задачи в смысле ограничений на её размерность. Какие задачи могут быть решены на ЭВМ за реальное время? | В начале 1960-х годов, в связи с началом широкого использования вычислительной техники для решения практических задач, возник вопрос о границах практической применимости данного алгоритма решения задачи в смысле ограничений на её размерность. Какие задачи могут быть решены на ЭВМ за реальное время? | ||
Ответ на этот вопрос был дан в работах Кобхэма (Alan Cobham, 1964) и Эдмондса (Jack Edmonds, 1965), где были введены сложностные классы задач. К ним относятся классы [[Класс P|P]], [[Классы NP и Σ₁|NP]] и т.д. | Ответ на этот вопрос был дан в работах Кобхэма (Alan Cobham, 1964) и Эдмондса (Jack Edmonds, 1965), где были введены сложностные классы задач. К ним относятся классы [[Класс P|P]], [[Классы NP и Σ₁|NP]] и т.д. |
Текущая версия на 19:03, 4 сентября 2022
В начале 1960-х годов, в связи с началом широкого использования вычислительной техники для решения практических задач, возник вопрос о границах практической применимости данного алгоритма решения задачи в смысле ограничений на её размерность. Какие задачи могут быть решены на ЭВМ за реальное время? Ответ на этот вопрос был дан в работах Кобхэма (Alan Cobham, 1964) и Эдмондса (Jack Edmonds, 1965), где были введены сложностные классы задач. К ним относятся классы P, NP и т.д.
Определения
В основных понятиях теории сложности используются такие величины, как время работы и объем затрачиваемой памяти.
Определение: |
машины Тьюринга на входе . | — время работы
Определение: |
— объем памяти, требуемый машине Тьюринга , для выполнения на входе . |
Для того, чтобы дать определения многим сложностным классам, понадобится определить такие классы, как и (префикс соответствует детерминизму).
Определение: |
— класс языков , для которых существует детеминированная машина Тьюринга такая, что и для любого выполнено (здесь — длина ). |
Определение: |
— класс языков , для которых существует детерминированная машина Тьюринга такая, что и для любого выполнено (здесь — длина ). |
Определение: |
— класс языков , для которых существует детерминированная программа такая, что и для любого выполнено и , где — длина входа. |
Аналогичным образом определяются классы и (префикс соответствует недетерминизму).
Определение: |
Недетерминированная машина Тьюринга (НМТ) — машина Тьюринга, в которой существует пара "ленточный символ - состояние", для которой существует 2 и более команд. |
Определение: |
— класс языков , для которых существует НМТ такая, что и для любого выполнено (здесь — длина ). |
Определение: |
— класс языков , для которых существует НМТ такая, что и для любого выполнено (здесь — длина ). |
См. также
Источники информации
- Википедия | Класс сложности
- Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений = Introduction to Automata Theory, Languages, and Computation. — М.: «Вильямс», 2002. — С. 528. — ISBN 0-201-44124-1.