02/02/2021

On the Complexity of Sum-of-Products Problems over Semirings

Thomas Eiter, Rafael Kiesel

Keywords:

Abstract Paper Similar Papers

Abstract: 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.

The video of this talk cannot be embedded. You can watch it here:
https://slideslive.com/38948477
(Link will open in new window)
 0
 0
 0
 0
  Share    
This is an embedded video. Talk and the respective paper are published at AAAI 2021 virtual conference. If you are one of the authors of the paper and want to manage your upload, see the question "My papertalk has been externally embedded..." in the FAQ section.

Comments

Post Comment
no comments yet
code of conduct: tbd Characters remaining: 140

Similar Papers

 0
 0
 0
 0
 15:27 
 0
 0
 0
 0
 13:25 
 0
 0
 0
 0
 2:54 
 0
 0
 0
 0
 18:47 
 0
 0
 0
 0
 11:08 
 0
 0
 0
 0
 21:02 
 0
 0
 0
 0
 5:25 
 0
 0
 0
 0
 17:45 
 0
 0
 0
 0
 19:03 
 0
 0
 0
 0
 19:39 
 0
 0
 0
 0
 5:15 
 0
 0
 0
 0
 9:30 
 0
 0
 0
 0
 15:01 
 0
 0
 0
 0
 15:27 
 0
 0
 0
 0
 15:07 
 0
 0
 0
 0
 13:19 
 0
 0
 0
 1
 3:28 
 0
 0
 0
 0
 15:51 
 0
 0
 0
 0
 15:12 
 0
 0
 0
 0
 3:22 
 0
 0
 0
 0
 3:21 
 0
 0
 0
 0
 9:41 
 0
 0
 0
 0
 3:22 
 0
 0
 0
 0
 15:04 
 0
 0
 0
 0
 18:04 
 0
 0
 0
 0
 25:07 
 0
 0
 0
 0
 16:38 
 0
 0
 0
 0
 17:01 
 0
 0
 0
 0
 5:40 
 0
 0
 0
 0
 5:25 
 0
 0
 0
 0
 10:41 
 0
 0
 0
 0
 4:43 
 0
 0
 0
 0
 13:30 
 0
 0
 0
 0
 15:02 
 0
 0
 0
 0
 4:56 
 0
 0
 0
 0
 3:18 
 0
 0
 0
 0
 14:47 
 0
 0
 0
 0
 16:25 
 0
 0
 0
 0
 13:55 
 0
 0
 0
 0
 3:24