315
правок
Изменения
запилил что-то
== Класс P ==
{{Определение
|definition=
'''Класс''' <tex>\mathrm{P}</tex> {{---}} класс языков (задач), разрешимых на детерминированной машине Тьюринга за полиномиальное время, то есть:
<tex>\mathrm{P} = \bigcup\limits_{p \in poly}DTIME(p(n))</tex>.
}}
Итого, язык <tex>L</tex> лежит в классе <tex>\mathrm{P}</tex> тогда и только тогда, когда существует такая детерминированная машина Тьюринга <tex>m</tex>, что:
# <tex>m</tex> завершает свою работу за полиномиальное время на любых входных данных;
# если на вход машине <tex>m</tex> подать слово <tex>l \in L</tex>, то она допустит его;
# если на вход машине <tex>m</tex> подать слово <tex>l \not\in L</tex>, то она не допустит его.
== Класс NP на языке недетерминированных машин и на языке сертификатов ==
{{Определение
|definition=<tex>\mathrm{NP}=\bigcup\limits_{p(n) \in poly}\mathrm{NTIME}(p(n))</tex>.
}}
То есть <tex>\mathrm{NP}</tex> — это множество языков, разрешимых недетерминированной программой за полиномиальное время.
{{Определение
|definition=<tex>\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\}</tex>.
}}
Нестрого говоря, <tex>\mathrm{\Sigma_1}</tex> — это множество языков, для которых существует работающая за полиномиальное время детерминированная программа-верификатор <tex>R(x,y)</tex>, а для каждого слова из языка (и только для слова из языка) можно предъявить сертификат полиномиальной длины, подтверждающий принадлежность слова языку и проверяемый верификатором.
== Сведение по Карпу ==
{{Определение
|definition =
<tex>D</tex> — класс языков, распознаваемых программами с некоторыми ограничениями. Тогда обозначим <tex>\widetilde{D}</tex> класс вычислимых функций, вычисляемых программами с теми же ограничениями.
}}
{{Определение
|definition =
'''Язык <tex>L_1</tex> <tex>\widetilde{D}</tex>-сводится по Карпу к языку <tex>L_2</tex> (<tex>L_1 \leq_{\widetilde{D}} L_2</tex>)''', если существует такая функция <tex>f</tex> из <tex>\widetilde{D}</tex>, что <tex>x</tex> принадлежит <tex>L_1</tex> тогда и только тогда, когда <tex>f(x)</tex> принадлежит <tex>L_2</tex>:<br>
<tex> (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 ) </tex>.
}}
== Видимо, это про NP-полные задачи ==
{{Определение
|definition =
<tex>C</tex> — сложностный класс, <tex>\widetilde{D}</tex> — класс вычислимых функций. Язык <tex>L</tex> называется '''<tex>C</tex>-трудным относительно <tex>\widetilde{D}</tex>-сведения (<tex>C</tex>-hard)''', если любой язык <tex>M</tex> из <tex>C</tex> <tex>\widetilde{D}</tex>-сводится к <tex>L</tex>:<br>
<tex> (L </tex> — <tex>C</tex>-hard <tex>) \overset{\underset{\mathrm{def}}{}}{\Leftrightarrow} ( \forall M \in C \Rightarrow M \leq_{f} L, f \in \widetilde{D} ) </tex>.
}}
{{Определение
|definition =
<tex>C</tex> — сложностный класс, <tex>\widetilde{D}</tex> — класс вычислимых функций. Язык <tex>L</tex> называется '''<tex>C</tex>-полным относительно <tex>\widetilde{D}</tex>-сведения (<tex>C</tex>-complete)''', если <tex>L</tex> является <tex>C</tex>-трудным относительно <tex>\widetilde{D}</tex>-сведения и сам лежит в <tex>C</tex>.
}}
'''Замечание.''' Часто используется сведение из <tex>\widetilde{P}</tex>, поэтому вместо «<tex>\widetilde{P}</tex>-сводится по Карпу» говорят просто «сводится». Также индекс у символа сведения обычно опускают.
Класс <tex>\mathrm{NP}</tex>-полных языков {{---}} <tex>\mathrm{NPC}</tex>.
<tex>\mathrm{NPC}</tex> является одним из важнейших классов в теории сложности, так как если найдется язык из этого класса, который также входит в класс <tex>\mathrm{P}</tex>,
тогда окажется, что <tex>\mathrm{P} = \mathrm{NP}</tex>.
== Класс coNP ==
В теории сложности '''класс co-NP''' — класс языков (задач), дополнение к которым лежит в '''[[NP]]'''.
'''co-NP''' = <tex>\Pi_1</tex> (См. [[Полиномиальная иерархия]])
== Вычисление с оракулом ==
В теории вычислений и теории сложности "машиной с оракулом" называют абстрактную машину, предназначенную для решения какой-либо проблемы разрешимости. Такая машина может быть представлена как машина Тьюринга, дополненная оракулом с неизвестным внутренним устройством. Постулируется, что оракул способен решить определенные проблемы разрешимости за один такт машины Тьюринга. Машина Тьюринга взаимодействует с оракулом путем записи на свою ленту входных данных для оракула и затем его запуском на исполнение. За один шаг оракул вычисляет функцию, стирает входные данные и пишет выходные данные на ленту. Иногда машина Тьюринга описывается как имеющая две ленты, одна предназначена для входных данных оракула, другая — для выходных.
{{Определение
|definition=
Оракул — абстракция, вычисляющая за <tex>O(1)</tex> времени, верно ли, что <tex>x</tex> принадлежит множеству <tex>A</tex>.
}}
Сложностный класс задач, решаемых алгоритмом из класса <tex>\mathrm{C}</tex> с оракулом для языка <tex>\mathrm{A}</tex>, обозначают <tex>\mathrm{C^A}</tex>.
== Класс PS ==
{{Определение
|definition=<tex>\mathrm{PS}</tex> <tex>\mathrm{(PSPACE)}</tex> {{---}} класс языков, разрешимых на детерминированной машине Тьюринга с использованием памяти полиномиального размера. <br>
<tex>\mathrm{PS}=\bigcup\limits_{p(n) \in poly} \mathrm{DSPACE}(p(n))</tex>.
}}
Если <tex>\mathrm{A}</tex> — множество языков, то <tex>\mathrm{C^A} =\bigcup\limits_{D \in A}\mathrm{C^D}</tex>.
== PS-полная задача ==
Видимо, [[Участник:SkudarnovYaroslav/Теормин к зачёту по теории сложности#Видимо, это про NP-полные задачи|тут]].
{{Определение
|definition=
'''Класс''' <tex>\mathrm{P}</tex> {{---}} класс языков (задач), разрешимых на детерминированной машине Тьюринга за полиномиальное время, то есть:
<tex>\mathrm{P} = \bigcup\limits_{p \in poly}DTIME(p(n))</tex>.
}}
Итого, язык <tex>L</tex> лежит в классе <tex>\mathrm{P}</tex> тогда и только тогда, когда существует такая детерминированная машина Тьюринга <tex>m</tex>, что:
# <tex>m</tex> завершает свою работу за полиномиальное время на любых входных данных;
# если на вход машине <tex>m</tex> подать слово <tex>l \in L</tex>, то она допустит его;
# если на вход машине <tex>m</tex> подать слово <tex>l \not\in L</tex>, то она не допустит его.
== Класс NP на языке недетерминированных машин и на языке сертификатов ==
{{Определение
|definition=<tex>\mathrm{NP}=\bigcup\limits_{p(n) \in poly}\mathrm{NTIME}(p(n))</tex>.
}}
То есть <tex>\mathrm{NP}</tex> — это множество языков, разрешимых недетерминированной программой за полиномиальное время.
{{Определение
|definition=<tex>\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\}</tex>.
}}
Нестрого говоря, <tex>\mathrm{\Sigma_1}</tex> — это множество языков, для которых существует работающая за полиномиальное время детерминированная программа-верификатор <tex>R(x,y)</tex>, а для каждого слова из языка (и только для слова из языка) можно предъявить сертификат полиномиальной длины, подтверждающий принадлежность слова языку и проверяемый верификатором.
== Сведение по Карпу ==
{{Определение
|definition =
<tex>D</tex> — класс языков, распознаваемых программами с некоторыми ограничениями. Тогда обозначим <tex>\widetilde{D}</tex> класс вычислимых функций, вычисляемых программами с теми же ограничениями.
}}
{{Определение
|definition =
'''Язык <tex>L_1</tex> <tex>\widetilde{D}</tex>-сводится по Карпу к языку <tex>L_2</tex> (<tex>L_1 \leq_{\widetilde{D}} L_2</tex>)''', если существует такая функция <tex>f</tex> из <tex>\widetilde{D}</tex>, что <tex>x</tex> принадлежит <tex>L_1</tex> тогда и только тогда, когда <tex>f(x)</tex> принадлежит <tex>L_2</tex>:<br>
<tex> (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 ) </tex>.
}}
== Видимо, это про NP-полные задачи ==
{{Определение
|definition =
<tex>C</tex> — сложностный класс, <tex>\widetilde{D}</tex> — класс вычислимых функций. Язык <tex>L</tex> называется '''<tex>C</tex>-трудным относительно <tex>\widetilde{D}</tex>-сведения (<tex>C</tex>-hard)''', если любой язык <tex>M</tex> из <tex>C</tex> <tex>\widetilde{D}</tex>-сводится к <tex>L</tex>:<br>
<tex> (L </tex> — <tex>C</tex>-hard <tex>) \overset{\underset{\mathrm{def}}{}}{\Leftrightarrow} ( \forall M \in C \Rightarrow M \leq_{f} L, f \in \widetilde{D} ) </tex>.
}}
{{Определение
|definition =
<tex>C</tex> — сложностный класс, <tex>\widetilde{D}</tex> — класс вычислимых функций. Язык <tex>L</tex> называется '''<tex>C</tex>-полным относительно <tex>\widetilde{D}</tex>-сведения (<tex>C</tex>-complete)''', если <tex>L</tex> является <tex>C</tex>-трудным относительно <tex>\widetilde{D}</tex>-сведения и сам лежит в <tex>C</tex>.
}}
'''Замечание.''' Часто используется сведение из <tex>\widetilde{P}</tex>, поэтому вместо «<tex>\widetilde{P}</tex>-сводится по Карпу» говорят просто «сводится». Также индекс у символа сведения обычно опускают.
Класс <tex>\mathrm{NP}</tex>-полных языков {{---}} <tex>\mathrm{NPC}</tex>.
<tex>\mathrm{NPC}</tex> является одним из важнейших классов в теории сложности, так как если найдется язык из этого класса, который также входит в класс <tex>\mathrm{P}</tex>,
тогда окажется, что <tex>\mathrm{P} = \mathrm{NP}</tex>.
== Класс coNP ==
В теории сложности '''класс co-NP''' — класс языков (задач), дополнение к которым лежит в '''[[NP]]'''.
'''co-NP''' = <tex>\Pi_1</tex> (См. [[Полиномиальная иерархия]])
== Вычисление с оракулом ==
В теории вычислений и теории сложности "машиной с оракулом" называют абстрактную машину, предназначенную для решения какой-либо проблемы разрешимости. Такая машина может быть представлена как машина Тьюринга, дополненная оракулом с неизвестным внутренним устройством. Постулируется, что оракул способен решить определенные проблемы разрешимости за один такт машины Тьюринга. Машина Тьюринга взаимодействует с оракулом путем записи на свою ленту входных данных для оракула и затем его запуском на исполнение. За один шаг оракул вычисляет функцию, стирает входные данные и пишет выходные данные на ленту. Иногда машина Тьюринга описывается как имеющая две ленты, одна предназначена для входных данных оракула, другая — для выходных.
{{Определение
|definition=
Оракул — абстракция, вычисляющая за <tex>O(1)</tex> времени, верно ли, что <tex>x</tex> принадлежит множеству <tex>A</tex>.
}}
Сложностный класс задач, решаемых алгоритмом из класса <tex>\mathrm{C}</tex> с оракулом для языка <tex>\mathrm{A}</tex>, обозначают <tex>\mathrm{C^A}</tex>.
== Класс PS ==
{{Определение
|definition=<tex>\mathrm{PS}</tex> <tex>\mathrm{(PSPACE)}</tex> {{---}} класс языков, разрешимых на детерминированной машине Тьюринга с использованием памяти полиномиального размера. <br>
<tex>\mathrm{PS}=\bigcup\limits_{p(n) \in poly} \mathrm{DSPACE}(p(n))</tex>.
}}
Если <tex>\mathrm{A}</tex> — множество языков, то <tex>\mathrm{C^A} =\bigcup\limits_{D \in A}\mathrm{C^D}</tex>.
== PS-полная задача ==
Видимо, [[Участник:SkudarnovYaroslav/Теормин к зачёту по теории сложности#Видимо, это про NP-полные задачи|тут]].
