Участник:SkudarnovYaroslav/Теормин к зачёту по теории сложности

Класс P

Определение:

Класс [math]\mathrm{P}[/math] — класс языков (задач), разрешимых на детерминированной машине Тьюринга за полиномиальное время, то есть: [math]\mathrm{P} = \bigcup\limits_{p \in poly}DTIME(p(n))[/math].

Итого, язык [math]L[/math] лежит в классе [math]\mathrm{P}[/math] тогда и только тогда, когда существует такая детерминированная машина Тьюринга [math]m[/math], что:

1. [math]m[/math] завершает свою работу за полиномиальное время на любых входных данных;
2. если на вход машине [math]m[/math] подать слово [math]l \in L[/math], то она допустит его;
3. если на вход машине [math]m[/math] подать слово [math]l \not\in L[/math], то она не допустит его.

Класс NP на языке недетерминированных машин и на языке сертификатов

Определение:

[math]\mathrm{NP}=\bigcup\limits_{p(n) \in poly}\mathrm{NTIME}(p(n))[/math].

То есть [math]\mathrm{NP}[/math] — это множество языков, разрешимых недетерминированной программой за полиномиальное время.

Определение:

[math]\mathrm{\Sigma_1}=\{L\bigm|\exists R(x,y)\in \tilde{\mathrm{P}}, p(n) - poly:x\in L\Leftrightarrow\exists y : |y|\le p(|x|), R(x,y)=1\}[/math].

Нестрого говоря, [math]\mathrm{\Sigma_1}[/math] — это множество языков, для которых существует работающая за полиномиальное время детерминированная программа-верификатор [math]R(x,y)[/math], а для каждого слова из языка (и только для слова из языка) можно предъявить сертификат полиномиальной длины, подтверждающий принадлежность слова языку и проверяемый верификатором.

Сведение по Карпу

Определение:

[math]D[/math] — класс языков, распознаваемых программами с некоторыми ограничениями. Тогда обозначим [math]\widetilde{D}[/math] класс вычислимых функций, вычисляемых программами с теми же ограничениями.

Определение:

Язык [math]L_1[/math] [math]\widetilde{D}[/math]-сводится по Карпу к языку [math]L_2[/math] ([math]L_1 \leq_{\widetilde{D}} L_2[/math]), если существует такая функция [math]f[/math] из [math]\widetilde{D}[/math], что [math]x[/math] принадлежит [math]L_1[/math] тогда и только тогда, когда [math]f(x)[/math] принадлежит [math]L_2[/math]: [math] (L_1 \leq_{\widetilde{D}} L_2) \overset{\underset{\mathrm{def}}{}}{\iff} ( \exists f \in \widetilde{D} : x \in L_1 \Leftrightarrow f(x) \in L_2 ) [/math].

Видимо, это про NP-полные задачи

Определение:

[math]C[/math] — сложностный класс, [math]\widetilde{D}[/math] — класс вычислимых функций. Язык [math]L[/math] называется [math]C[/math]-трудным относительно [math]\widetilde{D}[/math]-сведения ([math]C[/math]-hard), если любой язык [math]M[/math] из [math]C[/math] [math]\widetilde{D}[/math]-сводится к [math]L[/math]: [math] (L [/math] — [math]C[/math]-hard [math]) \overset{\underset{\mathrm{def}}{}}{\Leftrightarrow} ( \forall M \in C \Rightarrow M \leq_{f} L, f \in \widetilde{D} ) [/math].

Определение:

[math]C[/math] — сложностный класс, [math]\widetilde{D}[/math] — класс вычислимых функций. Язык [math]L[/math] называется [math]C[/math]-полным относительно [math]\widetilde{D}[/math]-сведения ([math]C[/math]-complete), если [math]L[/math] является [math]C[/math]-трудным относительно [math]\widetilde{D}[/math]-сведения и сам лежит в [math]C[/math].

Замечание. Часто используется сведение из [math]\widetilde{P}[/math], поэтому вместо «[math]\widetilde{P}[/math]-сводится по Карпу» говорят просто «сводится». Также индекс у символа сведения обычно опускают.

Класс [math]\mathrm{NP}[/math]-полных языков — [math]\mathrm{NPC}[/math]. [math]\mathrm{NPC}[/math] является одним из важнейших классов в теории сложности, так как если найдется язык из этого класса, который также входит в класс [math]\mathrm{P}[/math], тогда окажется, что [math]\mathrm{P} = \mathrm{NP}[/math].

Класс coNP

В теории сложности класс co-NP — класс языков (задач), дополнение к которым лежит в NP.

co-NP = [math]\Pi_1[/math] (См. Полиномиальная иерархия)

Вычисление с оракулом

В теории вычислений и теории сложности "машиной с оракулом" называют абстрактную машину, предназначенную для решения какой-либо проблемы разрешимости. Такая машина может быть представлена как машина Тьюринга, дополненная оракулом с неизвестным внутренним устройством. Постулируется, что оракул способен решить определенные проблемы разрешимости за один такт машины Тьюринга. Машина Тьюринга взаимодействует с оракулом путем записи на свою ленту входных данных для оракула и затем его запуском на исполнение. За один шаг оракул вычисляет функцию, стирает входные данные и пишет выходные данные на ленту. Иногда машина Тьюринга описывается как имеющая две ленты, одна предназначена для входных данных оракула, другая — для выходных.

Определение:

Оракул — абстракция, вычисляющая за [math]O(1)[/math] времени, верно ли, что [math]x[/math] принадлежит множеству [math]A[/math].

Сложностный класс задач, решаемых алгоритмом из класса [math]\mathrm{C}[/math] с оракулом для языка [math]\mathrm{A}[/math], обозначают [math]\mathrm{C^A}[/math].

Класс PS

Определение:

[math]\mathrm{PS}[/math] [math]\mathrm{(PSPACE)}[/math] — класс языков, разрешимых на детерминированной машине Тьюринга с использованием памяти полиномиального размера. [math]\mathrm{PS}=\bigcup\limits_{p(n) \in poly} \mathrm{DSPACE}(p(n))[/math].

Если [math]\mathrm{A}[/math] — множество языков, то [math]\mathrm{C^A} =\bigcup\limits_{D \in A}\mathrm{C^D}[/math].

PS-полная задача

Видимо, тут.