Image de couverture de livre

Decision DNNFs with imbalanced conjunction cannot efficiently represent CNFs of bounded width

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteur principal:	Razgon, Igor
Format:	Preprint
Publié:	2025
Sujets:	Computational Complexity
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

On complexity of restricted fragments of Decision DNNF
par: Calí, Andrea, et autres
Publié: (2025)

Small unsatisfiable $k$-CNFs with bounded literal occurrence
par: Zhang, Tianwei, et autres
Publié: (2024)

FPT Parameterisations of Fractional and Generalised Hypertree Width
par: Lanzinger, Matthias, et autres
Publié: (2025)

Searching for Falsified Clause in Random (log n)-CNFs is Hard for Randomized Communication
par: Riazanov, Artur, et autres
Publié: (2025)

Bounded-Depth Frege Lower Bounds for Random 3-CNFs via Deterministic Restrictions
par: Gryaznov, Svyatoslav, et autres
Publié: (2024)

Relative-error testing of conjunctions and decision lists
par: Chen, Xi, et autres
Publié: (2025)

Enumeration and updates for conjunctive linear algebra queries through expressibility
par: Muñoz, Thomas, et autres
Publié: (2023)

Space-bounded quantum state testing via space-efficient quantum singular value transformation
par: Gall, François Le, et autres
Publié: (2023)

Deterministic and Strongly Nondeterministic Decision Trees for Decision Tables from Closed Classes
par: Ostonov, Azimkhon, et autres
Publié: (2023)

Hazard-free Decision Trees
par: Benson, Deepu, et autres
Publié: (2025)

Lower bounds for planar Arithmetic Circuits
par: Ramya, C., et autres
Publié: (2025)

From FPT Decision to FPT Enumeration
par: Creignou, Nadia, et autres
Publié: (2025)

Simple general magnification of circuit lower bounds
par: Atserias, Albert, et autres
Publié: (2025)

Exponential lower bound via exponential sums
par: Bhattacharjee, Somnath, et autres
Publié: (2026)

Stable algorithms cannot reliably find isolated perceptron solutions
par: Gong, Shuyang, et autres
Publié: (2026)

Explaining the Ubiquity of Phase Transitions in Decision Problems
par: Jackson, Andrew
Publié: (2025)

Lower bounds on pure dynamic programming for connectivity problems on graphs of bounded path-width
par: Kluk, Kacper, et autres
Publié: (2025)

Depth lower bounds in Stabbing Planes for combinatorial principles
par: Dantchev, Stefan, et autres
Publié: (2021)

Search versus Decision for $\mathsf{S}_2^\mathsf{P}$
par: Fortnow, Lance
Publié: (2025)

The computational power of discrete chemical reaction networks with bounded executions
par: Doty, David, et autres
Publié: (2024)

Complexity lower bounds for succinct binary structures of bounded clique-width with restrictions
par: Geniet, Colin, et autres
Publié: (2026)

Phase Transitions in Decision Problems Over Odd-Sized Alphabets
par: Jackson, Andrew
Publié: (2025)

Upper and Lower Bounds on $T_1$ and $T_2$ Decision Tree Model
par: Alhamdan, Yousef M.
Publié: (2025)

Circuit metaconstruction in logspace for Rice-like complexity lower bounds in ANs and SGRs
par: Goubault-Larrecq, Aliénor, et autres
Publié: (2025)

A note on Jerabek's paper "A simplified lower bound for implicational logic"
par: Gordeev, Lev, et autres
Publié: (2026)

Lower Bounds on Cardinality of Reducts for Decision Tables from Closed Classes
par: Ostonov, Azimkhon, et autres
Publié: (2024)

The complexity of finding and enumerating optimal subgraphs to represent spatial correlation
par: Enright, Jessica, et autres
Publié: (2020)

Boolean Circuit Complexity and Two-Dimensional Cover Problems
par: Cavalar, Bruno P., et autres
Publié: (2025)

A nearly-$4\log n$ depth lower bound for formulas with restriction on top
par: Wu, Hao
Publié: (2024)

On Condensation of Block Sensitivity, Certificate Complexity and the $\mathsf{AND}$ (and $\mathsf{OR}$) Decision Tree Complexity
par: Nalli, Sai Soumya, et autres
Publié: (2026)

Fast and simple multiplication of bounded twin-width matrices
par: Kozma, László, et autres
Publié: (2026)

A linear bound for the size of the finite terminal assembly of a directed non-cooperative tile assembly system
par: Ivanov, Sergiu, et autres
Publié: (2024)

Decision algorithms for reversibility of one-dimensional non-linear cellular automata under null boundary conditions
par: Junchi, Ma, et autres
Publié: (2024)

$C_{2k+1}$-coloring of bounded-diameter graphs
par: Piecyk, Marta
Publié: (2024)

Query complexity lower bounds for local list-decoding and hard-core predicates (even for small rate and huge lists)
par: Ron-Zewi, Noga, et autres
Publié: (2024)

Debate is efficient with your time
par: Brown-Cohen, Jonah, et autres
Publié: (2026)

Lower bounds for set-blocked clauses proofs
par: Yolcu, Emre
Publié: (2024)

A characterization of efficiently compilable constraint languages
par: Berkholz, Christoph, et autres
Publié: (2023)

Decision Tree Learning on Product Spaces
par: Moakahr, Arshia Soltani, et autres
Publié: (2026)

Space-bounded online Kolmogorov complexity is additive
par: Bauwens, Bruno, et autres
Publié: (2025)