Изменения

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

Ответ на этот вопрос был дан в работах Кобмена Кобхэма (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> — недетерминизму)объем затрачиваемой памяти.

<tex>DTIME(f(n)) = \mathrm{ L \mid \exists </tex> программа <tex>p : LT}(p)=L,</tex> для любого <tex>x)</tex>, такого что <tex>|x| = n</tex>, где n — длина входа и <tex>Time(p,x) = O(f(n)) \}</tex>время работы программы р на входе х.

<tex>DSPACE(f(n)) = \mathrm{ L \mid \exists </tex> программа <tex>p : LS}(p)=L,</tex> для любого <tex>x)</tex>, такого что <tex>|x| = n</tex>, где n — длина входа и <tex>Space(pобъем памяти,x) = O(f(n)) \}</tex>требуемый программе р для выполнения на входе х.

Через Введём понятия классов <tex>DSPACE\mathrm{DTIME}</tex>, и <tex>DTIME\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>, в том числе классов [[Класс Pдля которых существует детерминированная программа <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>).}}{{Определение|P]] 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>). Классы NP }} {{Определение|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> и Σ₁|NP]]<tex>\mathrm{S}(p,x) = O(g(n))</tex>, где <tex>x</tex> — длина входа.}}

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

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