51
правка
Изменения
Новая страница: «==Определение== Язык <tex>A</tex> сводится по Куку к <tex>B</tex>, если существует разрешающая язык <tex>A…»
==Определение==
Язык <tex>A</tex> сводится по Куку к <tex>B</tex>, если существует разрешающая язык <tex>A</tex> программа <tex>m</tex>, работающая полиномиальное время от длины входа, которая может использовать разрешающую программу <tex>m_B</tex> для языка <tex>B</tex> в качестве оракула. Т.е. время работы <tex>m_B</tex> не учитывается.
Обозначается как <tex>A {\le}_c B</tex>
----
Класс <tex>P</tex> замкнут относительно сведения по Куку, т.к. и без обращения к оракулу программа <tex>m</tex> может разрешить сводимый язык.
Язык <tex>A</tex> сводится по Куку к <tex>B</tex>, если существует разрешающая язык <tex>A</tex> программа <tex>m</tex>, работающая полиномиальное время от длины входа, которая может использовать разрешающую программу <tex>m_B</tex> для языка <tex>B</tex> в качестве оракула. Т.е. время работы <tex>m_B</tex> не учитывается.
Обозначается как <tex>A {\le}_c B</tex>
----
Класс <tex>P</tex> замкнут относительно сведения по Куку, т.к. и без обращения к оракулу программа <tex>m</tex> может разрешить сводимый язык.
