Задача разрешимости (проблема разрешимости) — вопрос, сформулированный в рамках какой-либо формальной системы, требующий ответа «да» или «нет», возможно...

подмножеств. Формальное определение: задача разрешимости H {\displaystyle H} является NP-трудной, если любая задача L {\displaystyle L} из NP может быть...

Задача о максимальном разрезе (задача разрешимости) — задача ND16 в Приложении A2.2. Максимальный двудольный подграф (задача разрешимости) — задача GT25...

Задача о гамильтоновом пути и задача о гамильтоновом цикле — это задачи определения, существует ли гамильтонов путь или гамильтонов цикл в заданном графе...

Задача выполнимости формул в теориях (англ. satisfiability modulo theories, SMT) — это задача разрешимости для логических формул с учётом лежащих в их...

Поскольку задача поиска гамильтонова пути является NP-полной, это сведение показывает, что задачи поиска самого длинного пути в варианте разрешимости также...

Задача двудольной реализации — это классическая задача разрешимости в теории графов. Даны две конечные последовательности натуральных чисел ( a 1 , …...

классом NP (от англ. non-deterministic polynomial) называют множество задач разрешимости, решение которых возможно проверить на машине Тьюринга за время, не...

Зада́ча Коши́ — одна из основных задач теории дифференциальных уравнений (обыкновенных и с частными производными); состоит в нахождении решения (интеграла)...

Задача о реализации графа — задача разрешимости в теории графов. Задана конечная последовательность ( d 1 , … , d n ) {\displaystyle (d_{1},\dots ,d_{n})}...

противного": пусть есть некая задача, для которой требуется установить её неразрешимость. Тогда, предположим, что она разрешима, и попытаемся, используя этот...

подграфа для той же задачи. Это название делает упор на поиске таких подграфов, а не просто на разрешимости. Для доказательства, что задача поиска изоморфного...

сложности задач разрешимости, которые могут быть решены в детерминированной машине Тьюринга за полиномиальное время. NP: Класс сложности задач разрешимости, которые...

она или нет. Эквивалентно, это задача проверки, что заданное полуалгебраическое множество не пусто. Эта задача разрешимости является NP-трудной и лежит в...

Задача гамильтонова дополнения — это задача нахождения минимального числа рёбер, которое нужно добавить в граф, чтобы он стал гамильтоновым. Ясно, что...

знаменитых задач древности. История и современная теория. — Ростов: изд-во Ростовского университета, 1975. — 320 с. Манин Ю. И. О разрешимости задач на построение...

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

Чёрча — Тьюринга Вычислимая функция Разрешимое множество Алгоритмически неразрешимая задача Трансвычислительная задача Мальцев А. И. . Алгоритмы и рекурсивные...

Задача изоморфизма порождённому подграфу является NP-полной задачей разрешимости в теории сложности и теории графов. Задача заключается в поиске данного...

параметризованная задача — это подмножество L ⊆ Σ ∗ × N {\displaystyle L\subseteq \Sigma ^{*}\times \mathbb {N} } , описывающее задачу разрешимости. Параметрическая...

Задача о картинной галерее или музейная задача — это хорошо изученная задача видимости (просматриваемости) в вычислительной геометрии. Задача возникает...

Зада́ча Не́ймана, вторая краевая задача — в дифференциальных уравнениях краевая задача с заданными граничными условиями для производной искомой функции...

Для этого достаточно пройти тест числа на простоту. Эта задача детерминированно разрешима за полиномиальное время. В зависимости от сложности алгоритмы...

единственности решения задачи Коши, теоремы существования решения задачи Коши для гиперболических уравнений, теория разрешимости линейных уравнений используют...

(азерб. Sabir Mirzəyev) — азербайджанский специалист в области разрешимости краевых задач для операторно-дифференциальных уравнений и спектральной теории...

понятия алгоритма и решения задач об алгоритмической разрешимости, то есть, демонстрации алгоритмического решения задач в форме последовательности команд...

описанные формальные системы появились после того, как была поставлена задача Гильберта. Первые ФС появились после выхода книг Рассела и Уайтхеда «Формальные...

реагенты, которые позволяют трудно разрешимую задачу анализа сложных смесей привести к нескольким сравнительно простым задачам. Адсорбция Центрифугирование...

устройством. Постулируется, что оракул способен «угадать» решение проблемы разрешимости за одно обращение (один такт вызывающей его машины Тьюринга), после чего...

В теории сложности вычислений EQP (иногда называемый QP) — класс задач разрешимости, решаемых квантовым компьютером, который выводит правильный ответ с...

Задача о наименьшей окружности или задача о минимальном покрывающем круге — задача о вычислении наименьшей окружности, содержащей все заданные точки из...