[Back]

T. Eiter, R. Kiesel:
"On the Complexity of Sum-of-Products Problems over Semirings.";
Talk: 35th AAAI 2021, virtual event; 2021-02-02 - 2021-02-09; in: "Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, Thirty-Third Conference on Innovative Applications of Artificial Intelligence, IAAI 2021, The Eleventh Symposium on Educational Advances in Artificial Intelligence, EAAI 2021, Virtual Event, February 2-9, 2021", (2021), 6304 - 6311.

Many important problems in AI, among them SAT, #SAT, and probabilistic inference, amount to Sum-of-Products Problems, i.e. evaluating a sum of products of values from some semiring R. While efficiently solvable cases are known, a systematic study of the complexity of this problem is missing. We characterize the latter by NP(R), a novel generalization of NP over semiring R, and link it to well-known complexity classes. While NP(R) is unlikely to be contained in FPSPACE(POLY) in general, for a wide range of commutative (resp. in addition idempotent) semirings, there are reductions to #P (resp. NP) and solutions are thus only mildly harder to compute. We finally discuss NP(R)-complete reasoning problems in well-known semiring formalisms, among them Semiring-based Constraint Satisfaction Problems, obtaining new insights into their computational properties.

Viele wichtige Probleme in der KI, darunter SAT, #SAT und probabilistische Inferenz, laufen auf Sum-of-Products-Probleme hinaus, d.h. auf die Auswertung einer Summe von Produkten von Werten aus einem Semiring R. Während effizient lösbare Fälle bekannt sind, fehlt eine systematische Untersuchung der Komplexität dieses Problems. Wir charakterisieren dieses Problem durch NP(R), eine neue Verallgemeinerung von NP über einem Semiring R, und verbinden es mit bekannten Komplexitätsklassen. Während es unwahrscheinlich ist, dass NP(R) im Allgemeinen in FPSPACE(POLY) enthalten ist, gibt es für einen weiten Bereich von kommutativen (bzw. zusätzlich idempotenten) Semiringen Reduktionen auf #P (bzw. NP) und die Lösungen sind daher nur geringfügig schwieriger zu berechnen. Schließlich diskutieren wir NP(R)-komplette Probleme in bekannten Semiring-Formalismen, darunter Semiring-basierte Constraint-Satisfaction-Probleme, und gewinnen dabei neue Einsichten in deren Berechnungseigenschaften.

Semiring, Weighted Logic, Complexity, Sum-Of-Products

https://publik.tuwien.ac.at/files/publik_302155.pdf