Zobrazeno 1 - 10
of 141
pro vyhledávání: '"Beyersdorff, Olaf"'
Publikováno v:
In Artificial Intelligence November 2024 336
Autor:
Beyersdorff, Olaf, Böhm, Benjamin
Publikováno v:
Logical Methods in Computer Science, Volume 19, Issue 2 (April 14, 2023) lmcs:8519
QBF solvers implementing the QCDCL paradigm are powerful algorithms that successfully tackle many computationally complex applications. However, our theoretical understanding of the strength and limitations of these QCDCL solvers is very limited. In
Externí odkaz:
http://arxiv.org/abs/2109.04862
Publikováno v:
ACM Transactions on Computation Theory, Volume 16, Issue 2, Article No. 6 (March 2024)
We prove the first genuine QBF proof size lower bounds for the proof system Merge Resolution (MRes [Olaf Beyersdorff et al., 2020]), a refutational proof system for prenex quantified Boolean formulas (QBF) with a CNF matrix. Unlike most QBF resolutio
Externí odkaz:
http://arxiv.org/abs/2012.06779
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.
Publikováno v:
Logical Methods in Computer Science, Volume 15, Issue 1 (February 13, 2019) lmcs:4141
As a natural extension of the SAT problem, an array of proof systems for quantified Boolean formulas (QBF) have been proposed, many of which extend a propositional proof system to handle universal quantification. By formalising the construction of th
Externí odkaz:
http://arxiv.org/abs/1712.03626
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.
Publikováno v:
Logical Methods in Computer Science, Volume 13, Issue 2 (June 8, 2017) lmcs:2198
In sharp contrast to classical proof complexity we are currently short of lower bound techniques for QBF proof systems. In this paper we establish the feasible interpolation technique for all resolution-based QBF systems, whether modelling CDCL or ex
Externí odkaz:
http://arxiv.org/abs/1611.01328
We examine the existing Resolution systems for quantified Boolean formulas (QBF) and answer the question which of these calculi can be lifted to the more powerful Dependency QBFs (DQBF). An interesting picture emerges: While for QBF we have the stric
Externí odkaz:
http://arxiv.org/abs/1604.08058