Сложностные классы. Вычисления с оракулом — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 39 промежуточных версий 7 участников)
Строка 1: Строка 1:
В начале 1960-х годов, в связи с началом широкого использования вычислительной техники для решения практических задач, возник вопрос о границах практической применимости данного алгоритма решения задачи в смысле ограничений на ее размерность. Какие задачи могут быть решены на ЭВМ за реальное время?
+
В начале 1960-х годов, в связи с началом широкого использования вычислительной техники для решения практических задач, возник вопрос о границах практической применимости данного алгоритма решения задачи в смысле ограничений на её размерность. Какие задачи могут быть решены на ЭВМ за реальное время?
  
Ответ на этот вопрос был дан в работах Кобмена (Alan Cobham, 1964), и Эдмнодса (Jack Edmonds, 1965), где были введены сложностные классы задач. К ним относятся классы [[Класс P|P]], [[Недетерминированные вычисления. Классы NP и Σ₁|NP]] и т.д.
+
Ответ на этот вопрос был дан в работах Кобхэма (Alan Cobham, 1964) и Эдмондса (Jack Edmonds, 1965), где были введены сложностные классы задач. К ним относятся классы [[Класс P|P]], [[Классы NP и Σ₁|NP]] и т.д.
  
Для начала введем понятия <tex>DTIME</tex> и <tex>DSPACE</tex>, аналогичным образом определяются классы <tex>NSPACE</tex> и <tex>NTIME</tex> (префикс <tex>D</tex> соответствует детерминизму, а <tex>N</tex> — недетерминизму).
+
Слож­ность ал­го­рит­ма - ве­ли­чи­на, ха­ра­к­те­ри­зу­ющая дли­ну опи­са­ния ал­го­рит­ма или гро­мо­зд­кость про­цес­сов его при­ме­не­ния к ис­хо­дным дан­ным.
 +
 
 +
В основных понятиях теории сложности используются такие величины как время работы и объем затрачиваемой памяти.
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
<tex>DTIME(f(n)) = \{ L \mid \exists </tex> программа <tex>p : L(p)=L, \forall x</tex>, такого что <tex>|x| = n</tex> (здесь <tex>n</tex> — длина входа), <tex>Time(p,x) = O(f(n)) \}</tex>.
+
<tex>\mathrm{T}(p,x)</tex> — время работы программы р на входе х.
 
}}
 
}}
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
<tex>DSPACE(f(n)) = \{ L \mid \exists </tex> программа <tex>p : L(p)=L, \forall x</tex>, такого что <tex>|x| = n</tex> (здесь <tex>n</tex> — длина входа), <tex>Space(p,x) = O(f(n)) \}</tex>.
+
<tex>\mathrm{S}(p,x)</tex> — объем памяти, требуемый программе р для выполнения на входе х.
 
}}
 
}}
  
Через понятия классов <tex>DSPACE</tex>, <tex>DTIME</tex>, <tex>NSPACE</tex> и <tex>NTIME</tex> будет дано определение многим сложностным классам, в том числе классов [[Класс P|P]] и [[Недетерминированные вычисления. Классы NP и Σ₁|NP]].
+
Введём понятия <tex>\mathrm{DTIME}</tex> и <tex>\mathrm{DSPACE}</tex>, аналогичным образом определяются классы <tex>\mathrm{NSPACE}</tex> и <tex>\mathrm{NTIME}</tex> (префикс <tex>\mathrm{D}</tex> соответствует детерминизму, а <tex>\mathrm{N}</tex> — недетерминизму). Через них будет дано определение многим сложностным классам.
 +
 
 +
{{Определение
 +
|definition=
 +
<tex>\mathrm{DTIME}(f(n))</tex> — класс языков <tex>L</tex>, для которых существует детерминированная программа <tex>p</tex> такая, что <tex>L(p)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{T}(p,x) = O(f(n))</tex> (здесь <tex>n</tex> — длина <tex>x</tex>).
 +
}}
 +
{{Определение
 +
|definition=
 +
<tex>\mathrm{DSPACE}(f(n))</tex> — класс языков <tex>L</tex>, для которых существует детерминированная программа <tex>p</tex> такая, что <tex>L(p)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{S}(p,x) = O(f(n))</tex> (здесь <tex>n</tex> — длина <tex>x</tex>).
 +
}}
 +
 
 +
{{Определение
 +
|definition=
 +
<tex>\mathrm{TS}(f,g)</tex> — класс языков <tex>L</tex>, для которых существует детерминированная программа <tex>p</tex> такая, что <tex>L(p)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{T}(p,x) = O(f(n))</tex> и <tex>\mathrm{S}(p,x) = O(g(n))</tex>, где <tex>x</tex> — длина входа.
 +
}}
  
 
== Вычисление с оракулом ==
 
== Вычисление с оракулом ==
 +
В теории вычислений и теории сложности Машиной с оракулом называют абстрактную машину, предназначенную для решения какой-либо проблемы разрешимости. Такая машина может быть представлена как машина Тьюринга, дополненная оракулом с неизвестным внутренним устройством. Постулируется, что оракул способен решить определенные проблемы разрешимости за один такт машины Тьюринга. Машина Тьюринга взаимодействует с оракулом путем записи на свою ленту входных данных для оракула и затем запуском оракула на исполнение. За один шаг оракул вычисляет функцию, стирает входные данные и пишет выходные данные на ленту. Иногда машина Тьюринга описывается как имеющая две ленты, одна предназначена для входных данных оракула, другая — для выходных.
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Оракул — программа <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>\mathrm{C}</tex> с оракулом для языка <tex>\mathrm{A}</tex>, обозначают <tex>\mathrm{C^A}</tex>.  
Если <tex>A</tex> — это множество языков, то <tex>C^A =\bigcup\limits_{D \in A}C^D</tex>, где <tex>D</tex> — язык из <tex>A</tex>.
+
Если <tex>\mathrm{A}</tex> — множество языков, то <tex>\mathrm{C^A} =\bigcup\limits_{D \in A}\mathrm{C^D}</tex>.
 +
 
 +
[[Категория: Теория сложности]]

Текущая версия на 19:10, 4 сентября 2022

В начале 1960-х годов, в связи с началом широкого использования вычислительной техники для решения практических задач, возник вопрос о границах практической применимости данного алгоритма решения задачи в смысле ограничений на её размерность. Какие задачи могут быть решены на ЭВМ за реальное время?

Ответ на этот вопрос был дан в работах Кобхэма (Alan Cobham, 1964) и Эдмондса (Jack Edmonds, 1965), где были введены сложностные классы задач. К ним относятся классы P, NP и т.д.

Слож­ность ал­го­рит­ма - ве­ли­чи­на, ха­ра­к­те­ри­зу­ющая дли­ну опи­са­ния ал­го­рит­ма или гро­мо­зд­кость про­цес­сов его при­ме­не­ния к ис­хо­дным дан­ным.

В основных понятиях теории сложности используются такие величины как время работы и объем затрачиваемой памяти.

Определение:
[math]\mathrm{T}(p,x)[/math] — время работы программы р на входе х.


Определение:
[math]\mathrm{S}(p,x)[/math] — объем памяти, требуемый программе р для выполнения на входе х.


Введём понятия [math]\mathrm{DTIME}[/math] и [math]\mathrm{DSPACE}[/math], аналогичным образом определяются классы [math]\mathrm{NSPACE}[/math] и [math]\mathrm{NTIME}[/math] (префикс [math]\mathrm{D}[/math] соответствует детерминизму, а [math]\mathrm{N}[/math] — недетерминизму). Через них будет дано определение многим сложностным классам.


Определение:
[math]\mathrm{DTIME}(f(n))[/math] — класс языков [math]L[/math], для которых существует детерминированная программа [math]p[/math] такая, что [math]L(p)=L[/math] и для любого [math]x[/math] из [math]L[/math] выполнено [math]\mathrm{T}(p,x) = O(f(n))[/math] (здесь [math]n[/math] — длина [math]x[/math]).


Определение:
[math]\mathrm{DSPACE}(f(n))[/math] — класс языков [math]L[/math], для которых существует детерминированная программа [math]p[/math] такая, что [math]L(p)=L[/math] и для любого [math]x[/math] из [math]L[/math] выполнено [math]\mathrm{S}(p,x) = O(f(n))[/math] (здесь [math]n[/math] — длина [math]x[/math]).


Определение:
[math]\mathrm{TS}(f,g)[/math] — класс языков [math]L[/math], для которых существует детерминированная программа [math]p[/math] такая, что [math]L(p)=L[/math] и для любого [math]x[/math] из [math]L[/math] выполнено [math]\mathrm{T}(p,x) = O(f(n))[/math] и [math]\mathrm{S}(p,x) = O(g(n))[/math], где [math]x[/math] — длина входа.


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

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

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

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