Constrained Optimization Over Semirings

Explore the complexity of constraint optimization problems over semirings in this 29-minute lecture by Kuldeep Meel from the University of Toronto. Delve into the OptConf problem, which involves finding the maximum value of propositional formula interpretations over semirings. Learn about the FP^{NP} complexity class for Viterbi semirings and the FP^{NP[log]} hardness results. Examine similar complexity findings for tropical, fuzzy, and access control semirings. Discover potential opportunities for developing algorithmic procedures leveraging SAT solver capabilities. Gain insights into applications of logical formula interpretations over semirings in logic, AI, databases, and security.