On the Counting Version of the Maximum 2-Satisfiability Problem

V. Yu. Popov

Ural Federal University named after the First President of Russia B. N. Yeltsin, Ekaterinburg

Abstract: The counting version of the maximum 2-satisfiability problem is considered. A parsimonious reduction of the satisfiability problem to the maximum 2-satisfiability problem is constructed, proving the computational hardness of the counting version of the maximum 2-satisfiability problem.

Keywords: computational complexity, maximum 2-satisfiability problem, 3-satisfiability problem.

UDC: 510.52

MSC: 68Q25

Received: 29.03.2024
Revised: 01.12.2024

DOI: 10.4213/mzm14325

 English version: Mathematical Notes, 2025, 118:3, 593–601

Bibliographic databases:

•