Abstract
Interpretations of logical formulas over semirings, other than the Boolean semiring, have applications in areas such as AI, databases and security. These interpretations offer richer information beyond the simple truth or falsity of statements. In this talk, we will consider the following problem: Given a propositional formula F with n variables, find the maximum value over all possible interpretations of F over a given semiring K. The related search problem is to identify an interpretation that achieves the maximum value. We will explore the complexity of these problems over semirings other than the Boolean semiring.