  Interpretations of logical formulas over semirings have applications in
various areas of computer science including logic, AI, databases, and security.
Such interpretations provide richer information beyond the truth or falsity of
a statement. Examples of such semirings include Viterbi semiring, min-max or
access control semiring, tropical semiring, and fuzzy semiring.
  The present work investigates the complexity of constraint optimization
problems over semirings. The generic optimization problem we study is the
following: Given a propositional formula $\varphi$ over $n$ variable and a
semiring $(K,+,\cdot,0,1)$, find the maximum value over all possible
interpretations of $\varphi$ over $K$. This can be seen as a generalization of
the well-known satisfiability problem. A related problem is to find an
interpretation that achieves the maximum value. In this work, we first focus on
these optimization problems over the Viterbi semiring, which we call optConfVal
and optConf.
  We show that for general propositional formulas in negation normal form,
optConfVal and optConf are in ${\mathrm{FP}}^{\mathrm{NP}}$. We investigate
optConf when the input formula $\varphi$ is represented as a CNF. For CNF
formulae, we first derive an upper bound on optConfVal as a function of the
number of maximum satisfiable clauses. In particular, we show that if $r$ is
the maximum number of satisfiable clauses in a CNF formula with $m$ clauses,
then its optConfVal is at most $1/4^{m-r}$. Building on this we establish that
optConfVal for CNF formulae is hard for the complexity class
${\mathrm{FP}}^{\mathrm{NP}[\log]}$. We also design polynomial-time
approximation algorithms and establish an inapproximability for optConfVal. We
establish similar complexity results for these optimization problems over other
semirings including tropical, fuzzy, and access control semirings.
