Более быстрый доступ, чем браузер!
8 отношения: Контекстно-зависимая грамматика, Подмножество, Сведение по Карпу, Теорема Сэвича, Машина Тьюринга, Многочлен, Задача разрешимости, Вычислительная сложность.
Контекстно-зависимая грамматика
Контекстно-зависимая грамматика (КЗ-грамматика, контекстная грамматика) — частный случай формальной грамматики (тип 1 по иерархии Хомского), у которой левые и правые части всех продукций могут быть окружены терминальными и нетерминальными символами.
Новый!!: Класс PSPACE и Контекстно-зависимая грамматика · Узнать больше »
Подмножество
кругов Эйлера видно, что A является подмножеством B, а B является надмножеством A. Подмно́жество в теории множеств — это понятие части множества.
Новый!!: Класс PSPACE и Подмножество · Узнать больше »
Сведение по Карпу
Любой язык L_1 называется сводимым по Карпу к языку L_2, если существует функция F\colon \Sigma^* \mapsto \Sigma^*, вычисляемая за полиномиальное время, где F(x) принадлежит L_2 в том случае, если x принадлежит L_1.
Новый!!: Класс PSPACE и Сведение по Карпу · Узнать больше »
Теорема Сэвича
Теорема Сэвича (1970): То есть, если недетерминированная машина Тьюринга может решить проблему используя f(n) памяти, то детерминированная машина Тьюринга сможет это сделать за квадрат памяти.
Новый!!: Класс PSPACE и Теорема Сэвича · Узнать больше »
Машина Тьюринга
Художественное представление машины Тьюринга Маши́на Тью́ринга (МТ) — абстрактный исполнитель (абстрактная вычислительная машина).
Новый!!: Класс PSPACE и Машина Тьюринга · Узнать больше »
Многочлен
upright Многочле́н (или полино́м от πολυ- «много» + nomen «имя») от n переменных — это сумма одночленов или, строго, — конечная формальная сумма вида В частности, многочлен от одной переменной есть конечная формальная сумма вида С помощью многочлена выводятся понятия «алгебраическое уравнение» и «алгебраическая функция».
Новый!!: Класс PSPACE и Многочлен · Узнать больше »
Задача разрешимости
Задача разрешимости (проблема разрешимости) — вопрос, сформулированный в рамках какой-либо формальной системы, требующий ответа «да» или «нет», возможно, зависящего от значений некоторых входных параметров.
Новый!!: Класс PSPACE и Задача разрешимости · Узнать больше »
Вычислительная сложность
Вычисли́тельная сло́жность — понятие в информатике и теории алгоритмов, обозначающее функцию зависимости объёма работы, которая выполняется некоторым алгоритмом, от размера входных данных.
Новый!!: Класс PSPACE и Вычислительная сложность · Узнать больше »
