Abstract
Interpretations of logical formulas over semirings have applications in various areas of computer science including logic, AI, databases, and security. While work on the design of decision procedures over semirings dates to 90's, there is, surprisingly, a dearth of complexity-theoretic investigations. In this talk, I will present our work investigating the complexity of constraint optimization problems over semirings. We focus on the problem of OptConf, defined as follows:
Given a propositional formula F over n variable and a semiring (K,+,⋅,0,1), find the maximum value over all possible interpretations of F over K.
We show that OptConf is in FP^{NP} for Viterbi semirings, and it is hard for the complexity class FP^{NP[log]} -- thereby leaving open a tantalizing gap. We establish similar complexity results for these optimization problems over other semirings, including tropical, fuzzy, and access control semirings. Our work suggests exciting opportunities for developing algorithmic procedures that rely on SAT solvers' power.
Relevant Paper: https://arxiv.org/abs/2302.12937