Buchumschlag

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

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
1. Verfasser:	Razgon, Igor
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Computational Complexity
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

On complexity of restricted fragments of Decision DNNF
von: Calí, Andrea, et al.
Veröffentlicht: (2025)

Small unsatisfiable $k$-CNFs with bounded literal occurrence
von: Zhang, Tianwei, et al.
Veröffentlicht: (2024)

FPT Parameterisations of Fractional and Generalised Hypertree Width
von: Lanzinger, Matthias, et al.
Veröffentlicht: (2025)

Searching for Falsified Clause in Random (log n)-CNFs is Hard for Randomized Communication
von: Riazanov, Artur, et al.
Veröffentlicht: (2025)

Bounded-Depth Frege Lower Bounds for Random 3-CNFs via Deterministic Restrictions
von: Gryaznov, Svyatoslav, et al.
Veröffentlicht: (2024)

Relative-error testing of conjunctions and decision lists
von: Chen, Xi, et al.
Veröffentlicht: (2025)

Enumeration and updates for conjunctive linear algebra queries through expressibility
von: Muñoz, Thomas, et al.
Veröffentlicht: (2023)

Space-bounded quantum state testing via space-efficient quantum singular value transformation
von: Gall, François Le, et al.
Veröffentlicht: (2023)

Deterministic and Strongly Nondeterministic Decision Trees for Decision Tables from Closed Classes
von: Ostonov, Azimkhon, et al.
Veröffentlicht: (2023)

Hazard-free Decision Trees
von: Benson, Deepu, et al.
Veröffentlicht: (2025)

Lower bounds for planar Arithmetic Circuits
von: Ramya, C., et al.
Veröffentlicht: (2025)

From FPT Decision to FPT Enumeration
von: Creignou, Nadia, et al.
Veröffentlicht: (2025)

Simple general magnification of circuit lower bounds
von: Atserias, Albert, et al.
Veröffentlicht: (2025)

Exponential lower bound via exponential sums
von: Bhattacharjee, Somnath, et al.
Veröffentlicht: (2026)

Stable algorithms cannot reliably find isolated perceptron solutions
von: Gong, Shuyang, et al.
Veröffentlicht: (2026)

Explaining the Ubiquity of Phase Transitions in Decision Problems
von: Jackson, Andrew
Veröffentlicht: (2025)

Lower bounds on pure dynamic programming for connectivity problems on graphs of bounded path-width
von: Kluk, Kacper, et al.
Veröffentlicht: (2025)

Depth lower bounds in Stabbing Planes for combinatorial principles
von: Dantchev, Stefan, et al.
Veröffentlicht: (2021)

Search versus Decision for $\mathsf{S}_2^\mathsf{P}$
von: Fortnow, Lance
Veröffentlicht: (2025)

The computational power of discrete chemical reaction networks with bounded executions
von: Doty, David, et al.
Veröffentlicht: (2024)

Complexity lower bounds for succinct binary structures of bounded clique-width with restrictions
von: Geniet, Colin, et al.
Veröffentlicht: (2026)

Phase Transitions in Decision Problems Over Odd-Sized Alphabets
von: Jackson, Andrew
Veröffentlicht: (2025)

Upper and Lower Bounds on $T_1$ and $T_2$ Decision Tree Model
von: Alhamdan, Yousef M.
Veröffentlicht: (2025)

Circuit metaconstruction in logspace for Rice-like complexity lower bounds in ANs and SGRs
von: Goubault-Larrecq, Aliénor, et al.
Veröffentlicht: (2025)

A note on Jerabek's paper "A simplified lower bound for implicational logic"
von: Gordeev, Lev, et al.
Veröffentlicht: (2026)

Lower Bounds on Cardinality of Reducts for Decision Tables from Closed Classes
von: Ostonov, Azimkhon, et al.
Veröffentlicht: (2024)

The complexity of finding and enumerating optimal subgraphs to represent spatial correlation
von: Enright, Jessica, et al.
Veröffentlicht: (2020)

Boolean Circuit Complexity and Two-Dimensional Cover Problems
von: Cavalar, Bruno P., et al.
Veröffentlicht: (2025)

A nearly-$4\log n$ depth lower bound for formulas with restriction on top
von: Wu, Hao
Veröffentlicht: (2024)

On Condensation of Block Sensitivity, Certificate Complexity and the $\mathsf{AND}$ (and $\mathsf{OR}$) Decision Tree Complexity
von: Nalli, Sai Soumya, et al.
Veröffentlicht: (2026)

Fast and simple multiplication of bounded twin-width matrices
von: Kozma, László, et al.
Veröffentlicht: (2026)

A linear bound for the size of the finite terminal assembly of a directed non-cooperative tile assembly system
von: Ivanov, Sergiu, et al.
Veröffentlicht: (2024)

Decision algorithms for reversibility of one-dimensional non-linear cellular automata under null boundary conditions
von: Junchi, Ma, et al.
Veröffentlicht: (2024)

$C_{2k+1}$-coloring of bounded-diameter graphs
von: Piecyk, Marta
Veröffentlicht: (2024)

Query complexity lower bounds for local list-decoding and hard-core predicates (even for small rate and huge lists)
von: Ron-Zewi, Noga, et al.
Veröffentlicht: (2024)

Debate is efficient with your time
von: Brown-Cohen, Jonah, et al.
Veröffentlicht: (2026)

Lower bounds for set-blocked clauses proofs
von: Yolcu, Emre
Veröffentlicht: (2024)

A characterization of efficiently compilable constraint languages
von: Berkholz, Christoph, et al.
Veröffentlicht: (2023)

Decision Tree Learning on Product Spaces
von: Moakahr, Arshia Soltani, et al.
Veröffentlicht: (2026)

Space-bounded online Kolmogorov complexity is additive
von: Bauwens, Bruno, et al.
Veröffentlicht: (2025)