Zobrazeno 1 - 10
of 47
pro vyhledávání: '"Theory of computation → Proof complexity"'
Autor:
Beyersdorff, Olaf, Böhm, Benjamin
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:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::51b214ee62f1aac251c4b49b7596b301
https://doi.org/10.46298/lmcs-19(2:2)2023
https://doi.org/10.46298/lmcs-19(2:2)2023
Autor:
Davis, Ben, Robere, Robert
Recent work has shown that many of the standard TFNP classes - such as PLS, PPADS, PPAD, SOPL, and EOPL - have corresponding proof systems in propositional proof complexity, in the sense that a total search problem is in the class if and only if the
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::1b90b9f26edc19cc62f7a4fa6dbbfcad
The Tensor Isomorphism problem (TI) has recently emerged as having connections to multiple areas of research within complexity and beyond, but the current best upper bound is essentially the brute force algorithm. Being an algebraic problem, TI (or r
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::d04eef1c7dbbc32f5dc1d8aebe3b63bf
Autor:
Austrin, Per, Risse, Kilian
We prove lower bounds for the Minimum Circuit Size Problem (MCSP) in the Sum-of-Squares (SoS) proof system. Our main result is that for every Boolean function f: {0,1}ⁿ → {0,1}, SoS requires degree Ω(s^{1-ε}) to prove that f does not have circu
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::24866a31890db2ccff16265ff80f8d9b
This report documents the program and the outcomes of Dagstuhl Seminar 22411 "Theory and Practice of SAT and Combinatorial Solving". The purpose of this workshop was to explore the Boolean satisfiability (SAT) problem, which plays a fascinating dual
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::234ba046fbad6ad0d1e8f1bd9e4895d4
For every prime p > 0, every n > 0 and κ = O(log n), we show the existence of an unsatisfiable system of polynomial equations over O(n log n) variables of degree O(log n) such that any Polynomial Calculus refutation over 𝔽_p with M extension vari
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::de0377b25bdee5ff333db9140d9eaafd
Autor:
Freitag, Cody, Komargodski, Ilan
In recent years, the number of applications of the repeated squaring assumption has been growing rapidly. The assumption states that, given a group element x, an integer T, and an RSA modulus N, it is hard to compute x^2^T mod N - or even decide whet
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::7fe402939d6a546f5bf2bafbc47f6d23
Autor:
Chede, Sravanthi, Shukla, Anil
Merge Resolution (MRes [Olaf Beyersdorff et al., 2021]) is a recently introduced proof system for false QBFs. Unlike other known QBF proof systems, it builds winning strategies for the universal player (countermodels) within the proofs as merge maps.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::a0b7da92ff71bb1b04f644b85a9d1dab
Autor:
Yolcu, Emre, Heule, Marijn J. H.
We study the complexity of proof systems augmenting resolution with inference rules that allow, given a formula Γ in conjunctive normal form, deriving clauses that are not necessarily logically implied by Γ but whose addition to Γ preserves satisf
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::4dc78d1d6a58d8098aec718de00c8486
http://arxiv.org/abs/2211.12456
http://arxiv.org/abs/2211.12456
Autor:
Chew, Leroy, Slivovsky, Friedrich
We pioneer a new technique that allows us to prove a multitude of previously open simulations in QBF proof complexity. In particular, we show that extended QBF Frege p-simulates clausal proof systems such as IR-Calculus, IRM-Calculus, Long-Distance Q
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::3b9dc2471b19f88c7cc7d4df4ff34733
http://arxiv.org/abs/2210.07085
http://arxiv.org/abs/2210.07085