Complexity of Weighted First-Order Model Counting in the Two-Variable Fragment with Counting Quantifiers: A Bound to Beat

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F24%3A00378130" target="_blank" >RIV/68407700:21230/24:00378130 - isvavai.cz</a>

Result on the web

<a href="https://doi.org/10.24963/kr.2024/64" target="_blank" >https://doi.org/10.24963/kr.2024/64</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.24963/kr.2024/64" target="_blank" >10.24963/kr.2024/64</a>

Result language

angličtina

Original language name

Complexity of Weighted First-Order Model Counting in the Two-Variable Fragment with Counting Quantifiers: A Bound to Beat

Original language description

We study the time complexity of weighted first-order model counting (WFOMC) over the logical language with two variables and counting quantifiers. The problem is known to be solvable in time polynomial in the domain size. However, the degree of the polynomial, which turns out to be relatively high for most practical applications, has never been properly addressed. First, we formulate a time complexity bound for the existing techniques for solving WFOMC with counting quantifiers. The bound is already known to be a polynomial with its degree depending on the number of cells of the input formula. We observe that the number of cells depends, in turn, exponentially on the parameters of the counting quantifiers appearing in the formula. Second, we propose a new approach to dealing with counting quantifiers, reducing the exponential dependency to a quadratic one, therefore obtaining a tighter upper bound. It remains an open question whether the dependency of the polynomial degree on the counting quantifiers can be reduced further, thus making our new bound a bound to beat.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

—

Continuities

S - Specificky vyzkum na vysokych skolach

Publication year

2024

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

Proceedings of the 21st International Conference on Principles of Knowledge Representation and Reasoning

ISBN

978-1-956792-05-8

ISSN

2334-1033

e-ISSN

2334-1033

Number of pages

11

Pages from-to

676-686

Publisher name

International Joint Conferences on Artificial Intelligence Organization

Place of publication

—

Event location

Hanoi

Event date

Nov 2, 2024

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—