В. Г. Дурнев, О. В. Зеткина, А. И. Зеткина, Д. М. Мурин, “О coNP-полноте задачи “Инъективный рюкзак””, ПДМ, 2016, номер 3(33),страницы 85

Математические основы информатики и программирования

О coNP-полноте задачи “Инъективный рюкзак”

В. Г. Дурнев, О. В. Зеткина, А. И. Зеткина, Д. М. Мурин

Ярославский государственный университет им. П. Г. Демидова, г. Ярославль, Россия

Аннотация: Устанавливается coNP-полнота задачи “Инъективный рюкзак”.

Ключевые слова: NP-полные и coNP-полные задачи, инъективный рюкзак, $m$-инъективный рюкзак.

УДК: 512.54

DOI: 10.17223/20710410/33/7