Изменения

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

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

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

==В основных понятиях теории сложности используются такие величины как время работы и объем затрачиваемой памяти.{{Определение=|definition=Классом <tex>DTIME\mathrm{T}(f(n)p,x)</tex> называется множество языков, для которых существует машина Тьюринга такая, что она всегда останавливается, и — время ее работы не превосходит программы р на входе х.}}{{Определение|definition=<tex>f\mathrm{S}(np,x)</tex>— объем памяти, где <tex>n</tex> — длина входатребуемый программе р для выполнения на входе х. Формально, определение можно записать так: }}

Введём понятия <tex>\mathrm{DTIME(f(n)) = }</tex> и <tex>\mathrm{ L DSPACE}</tex>, аналогичным образом определяются классы <tex>\mid \exists mathrm{NSPACE}</tex> машина Тьюринга и <tex>m : L(m)=L, Time(m,x) \le f(|x|) \mathrm{NTIME}</tex>, где (префикс <tex>|x|\mathrm{D}</tex> &mdash; длина входа соответствует детерминизму, а <tex>x\mathrm{N}</tex>— недетерминизму). Через них будет дано определение многим сложностным классам.

=={{Определение=|definition=Классом <tex>DSPACE\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 \mid \exists </tex> машина Тьюринга , для которых существует детерминированная программа <tex>p</tex> такая, что <tex>m : L(mp)=L, Space</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{S}(mp,x) \le = O(f(|n))</tex> (здесь <tex>n</tex> — длина <tex>x|) \}</tex>).}}

Аналогичным образом введем классы == Вычисление с оракулом ==В теории вычислений и теории сложности Машиной с оракулом называют абстрактную машину, предназначенную для решения какой-либо проблемы разрешимости. Такая машина может быть представлена как машина Тьюринга, дополненная оракулом с неизвестным внутренним устройством. Постулируется, что оракул способен решить определенные проблемы разрешимости за один такт машины Тьюринга. Машина Тьюринга взаимодействует с оракулом путем записи на свою ленту входных данных для оракула и затем запуском оракула на исполнение. За один шаг оракул вычисляет функцию, стирает входные данные и пишет выходные данные на ленту. Иногда машина Тьюринга описывается как имеющая две ленты, одна предназначена для входных данных оракула, другая — для выходных.{{Определение|definition=Оракул — программа <tex>NSPACEA(x)</tex> и , вычисляющая за <tex>NTIMEO(1)</tex>времени, верно ли, использующие недетерминированную машину Тьюринга взамен детерминированной (префикс что <tex>Dx \in A</tex> соответствует детерминизму.}}Сложностный класс задач, а решаемых алгоритмом из класса <tex>N\mathrm{C}</tex> — недетерминизму).  Через понятия классов с оракулом для языка <tex>DSPACE\mathrm{A}</tex>, обозначают <tex>DTIME\mathrm{C^A}</tex>, . Если <tex>NSPACE\mathrm{A}</tex> и — множество языков, то <tex>NTIME\mathrm{C^A} =\bigcup\limits_{D \in A}\mathrm{C^D}</tex> будет дано определение многим сложностным классам, в том числе классов [[Класс P|P]] и [[Недетерминированные вычисления. Классы NP и Σ₁|NP]].