• Classified by Research Topic • Sorted by Date • Classified by Publication Type •
Constraint Optimization over Semirings.
A. Pavan ⓡ Kuldeep S. Meel ⓡ N. V. Vinodchandran ⓡ Arnab Bhattacharyya.
In Proceedings of AAAI Conference on Artificial Intelligence (AAAI), January 2023.
The interpretation of logical formulas over semirings, which provide more information than simply the truth or falsity of a statement, have applications in computer science fields such as AI, databases, security, and logic. These semirings include the Viterbi semiring, the min-max or access control semiring, the tropical semiring, and the fuzzy semiring. This work explores the complexity of constraint optimization problems over semirings. The generic optimization problem studied is: given a propositional formula $\varphi$ over $n$ variables and a semiring $(K, +, \cdot, 0, 1)$, find the maximum value of all possible interpretations of $\varphi$ over $K$. This can be seen as a generalization of the well-known satisfiability problem, where a propositional formula is satisfiable if and only if the maximum value over all interpretations/assignments over the Boolean semiring is 1. A related problem is to find an interpretation that achieves the maximum value. This work focuses on these optimization problems over the Viterbi semiring, which are called optConfVal and optConf. It is shown that for general propositional formulas in negation normal form, optConfVal and optConf are in FPNP. When the input formula $\varphi$ is represented in conjunctive normal form, the complexity of optConf is investigated. For CNF formulae, an upper bound on the value of optConf as a function of the number of maximum satisfiable clauses is derived. It is shown that if $r$ is the maximum number of satisfiable clauses in a CNF formula with $m$ clauses, then its optConf value is at most $\frac14m-r$. Based on this result, it is established that optConf for CNF formulae is hard for the complexity class FPNP[log]. Polynomial-time approximation algorithms are also designed, and the inapproximability of optConfVal is established. Similar complexity results for these optimization problems over other semirings, such as the tropical, fuzzy, and access control semirings, are also established.
@inproceedings{PMVB23,
title={Constraint Optimization over Semirings},
author={Pavan, A. and Meel, Kuldeep S. and Vinodchandran, N. V. and Bhattacharyya, Arnab},
month=jan,
nameorder={random},
bib2html_dl_pdf={../Papers/aaai23-pmvb.pdf},
year={2023},
booktitle=AAAI,
bib2html_rescat={Misc},
bib2html_pubtype={Refereed Conference},
abstract={The interpretation of logical formulas over semirings, which provide more information than simply the truth or falsity of a statement, have applications in computer science fields such as AI, databases, security, and logic. These semirings include the Viterbi semiring, the min-max or access control semiring, the tropical semiring, and the fuzzy semiring. This work explores the complexity of constraint optimization problems over semirings. The generic optimization problem studied is: given a propositional formula $\varphi$ over $n$ variables and a semiring $(K, +, \cdot, 0, 1)$, find the maximum value of all possible interpretations of $\varphi$ over $K$. This can be seen as a generalization of the well-known satisfiability problem, where a propositional formula is satisfiable if and only if the maximum value over all interpretations/assignments over the Boolean semiring is 1. A related problem is to find an interpretation that achieves the maximum value. This work focuses on these optimization problems over the Viterbi semiring, which are called optConfVal and optConf. It is shown that for general propositional formulas in negation normal form, optConfVal and optConf are in FPNP. When the input formula $\varphi$ is represented in conjunctive normal form, the complexity of optConf is investigated. For CNF formulae, an upper bound on the value of optConf as a function of the number of maximum satisfiable clauses is derived. It is shown that if $r$ is the maximum number of satisfiable clauses in a CNF formula with $m$ clauses, then its optConf value is at most $\frac{1}{4m-r}$. Based on this result, it is established that optConf for CNF formulae is hard for the complexity class FPNP[log]. Polynomial-time approximation algorithms are also designed, and the inapproximability of optConfVal is established. Similar complexity results for these optimization problems over other semirings, such as the tropical, fuzzy, and access control semirings, are also established.},
keywords={Misc},
}
Generated by bib2html.pl (written by Patrick Riley with layout from Sanjit A. Seshia ) on Sun Apr 14, 2024 11:15:51