Сведение задачи #2SAT к монотонному случаю с увеличением количества переменных. Некоторые классы монотонных биюнктивных функций полиномиально вычислимого веса

Дискретная математика 2026

View at publisher
Authors: Nikita M Trubitsin
DOI: 10.4213/dm1853
Cited by: 0
References: 14

Abstract

В статье предложен метод сведения задачи нахождения веса произвольной 2-КНФ к задаче вычисления веса монотонной 2-КНФ. Получены точные значения весов монотонных биюнктивных функций специального вида.

Fields of Study & Subjects

Complexity and Algorithms in Graphs Advanced Graph Theory Research Advanced Combinatorial Mathematics

Publication details

Journal / source
Дискретная математика
Volume
38
Issue
1
Pages
135–156
Publication date
1 January 2026
Language
RU