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

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

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

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

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

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

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

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

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

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

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

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

пары в обратном порядке. Задача минимизации вероятности застревания с учётом того, что нижние фишки не видны, PSPACE-полная. Задача решения головоломки, когда...

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

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

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

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

Задача о вершинном покрытии — NP-полная задача информатики в области теории графов. Часто используется в теории сложности для доказательства NP-полноты...

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

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

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

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

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

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

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

{\displaystyle n>4} ? Эта задача решена лишь для n = 8 {\displaystyle n=8} (240) и n = 24 {\displaystyle n=24} (196 560). Задача плотнейшей упаковки шаров...

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

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

аппроксимации задач оптимизации играет похожую роль, какую играет полиномиальное приведение[англ.] при изучении вычислительной сложности задач разрешимости. Возможность...

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

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