Сложностные классы. Вычисления с оракулом — различия между версиями
Строка 20: | Строка 20: | ||
Оракул — программа <tex>A(x)</tex>, вычисляющая за <tex>O(1)</tex> верно ли, что <tex>x \in A</tex>. | Оракул — программа <tex>A(x)</tex>, вычисляющая за <tex>O(1)</tex> верно ли, что <tex>x \in A</tex>. | ||
}} | }} | ||
− | Сложностный класс задач, решаемых алгоритмом из класса <tex>C</tex> с оракулом для языка <tex>A</tex> обозначают <tex>C^A</tex>. Так же <tex>C</tex> называют сложностным классом с доступом к оракулу <tex>A</tex>. | + | Сложностный класс задач, решаемых алгоритмом из класса <tex>C</tex> с оракулом для языка <tex>A</tex>, обозначают <tex>C^A</tex>. Так же <tex>C</tex> называют сложностным классом с доступом к оракулу <tex>A</tex>. |
Если <tex>A</tex> — это множество языков, то <tex>C^A =\bigcup\limits_{D \in A}C^D</tex>, где <tex>D</tex> — язык из <tex>A</tex>. | Если <tex>A</tex> — это множество языков, то <tex>C^A =\bigcup\limits_{D \in A}C^D</tex>, где <tex>D</tex> — язык из <tex>A</tex>. |
Версия 19:11, 14 мая 2012
В начале 1960-х годов, в связи с началом широкого использования вычислительной техники для решения практических задач, возник вопрос о границах практической применимости данного алгоритма решения задачи в смысле ограничений на ее размерность. Какие задачи могут быть решены на ЭВМ за реальное время?
Ответ на этот вопрос был дан в работах Кобмена (Alan Cobham, 1964), и Эдмнодса (Jack Edmonds, 1965), где были введены сложностные классы задач. К ним относятся классы P, NP и т.д.
Для начала введем понятия
и , аналогичным образом определяются классы и (префикс соответствует детерминизму, а — недетерминизму).Определение: |
программа и для , такого что (здесь — длина входа), . |
Определение: |
программа и для , такого что (здесь — длина входа), . |
Через понятия классов , , и будет дано определение многим сложностным классам, в том числе классов P и NP.
Вычисление с оракулом
Определение: |
Оракул — программа | , вычисляющая за верно ли, что .
Сложностный класс задач, решаемых алгоритмом из класса
с оракулом для языка , обозначают . Так же называют сложностным классом с доступом к оракулу . Если — это множество языков, то , где — язык из .