О количественной версии проблемы максимальной 2-выполнимости

В. Ю. Попов

Уральский федеральный университет им. первого Президента России Б. Н. Ельцина, г. Екатеринбург

Аннотация: В работе рассматривается количественная версия проблемы максимальной 2-выполнимости. Построена экономная сводимость от проблемы выполнимости к проблеме максимальной 2-выполнимости, что, как следствие, доказывает вычислительную трудность количественной версии проблемы максимальной 2-выполнимости.
Библиография: 24 названия.

Ключевые слова: вычислительная сложность, проблема максимальной 2-выполнимости, проблема 3-выполнимости.

УДК: 510.52

MSC: 68Q25

Поступило: 29.03.2024
Исправленный вариант: 01.12.2024

DOI: 10.4213/mzm14325

 Англоязычная версия: Mathematical Notes, 2025, 118:3, 593–601

Реферативные базы данных:

•