Cover Image

The 2CNF Boolean Formula Satisfiability Problem and the Linear Space Hypothesis

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Yamakami, Tomoyuki
Format:	Preprint
Published:	2017
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Quantum First-Order Logics That Capture Logarithmic-Time/Space Quantum Computability
by: Yamakami, Tomoyuki
Published: (2025)

Logical Expressibility of Syntactic NL for Complementarity, Monotonicity, and Maximization
by: Yamakami, Tomoyuki
Published: (2024)

Complexity Classification of Complex-Weighted Counting Acyclic Constraint Satisfaction Problems
by: Yamakami, Tomoyuki
Published: (2024)

Between SC and LOGDCFL: Families of Languages Accepted by Logarithmic-Space Deterministic Auxiliary Depth-k Storage Automata
by: Yamakami, Tomoyuki
Published: (2022)

Elementary Quantum Recursion Schemes That Capture Quantum Polylogarithmic Time Computability of Quantum Functions
by: Yamakami, Tomoyuki
Published: (2023)

Nonuniform Families of Polynomial-Size Quantum Finite Automata and Quantum Logarithmic-Space Computation with Polynomial-Size Advice
by: Yamakami, Tomoyuki
Published: (2019)

Inverse Intersections for Boolean Satisfiability Problems
by: Homer, Paul W.
Published: (2025)

A Schematic Definition of Quantum Polynomial Time Computability
by: Yamakami, Tomoyuki
Published: (2018)

Unambiguous and Co-Nondeterministic Computations of Finite Automata and Pushdown Automata Families and the Effects of Multiple Counters
by: Yamakami, Tomoyuki
Published: (2024)

Power of Counting by Nonuniform Families of Polynomial-Size Finite Automata
by: Yamakami, Tomoyuki
Published: (2023)

Intersection and Union Hierarchies of Deterministic Context-Free Languages and Pumping Lemmas
by: Yamakami, Tomoyuki
Published: (2021)

The No Endmarker Theorem for One-Way Probabilistic Pushdown Automata
by: Yamakami, Tomoyuki
Published: (2021)

Nondeterministic Auxiliary Depth-Bounded Storage Automata and Semi-Unbounded Fan-in Cascading Circuits
by: Yamakami, Tomoyuki
Published: (2024)

How Does Adiabatic Quantum Computation Fit into Quantum Automata Theory?
by: Yamakami, Tomoyuki
Published: (2020)

Compression with wildcards: All models of a Boolean 2-CNF
by: Wild, Marcel
Published: (2012)

Learning-Augmented Algorithms for Boolean Satisfiability
by: Attias, Idan, et al.
Published: (2025)

On the Satisfaction Probabilities of $k$-CNF Formulas
by: Tantau, Till
Published: (2022)

Hard CNF Instances for Ideal Proof Systems
by: Hakoniemi, Tuomas, et al.
Published: (2026)

Model Counting for Dependency Quantified Boolean Formulas
by: Fung, Long-Hin, et al.
Published: (2025)

On Extremal Properties of k-CNF: Capturing Threshold Functions
by: Gurumukhani, Mohit, et al.
Published: (2024)

Solving Quantified Boolean Formulas with Few Existential Variables
by: Eriksson, Leif, et al.
Published: (2024)

Local Correction of Linear Functions over the Boolean Cube
by: Amireddy, Prashanth, et al.
Published: (2024)

Boolean Circuit Complexity and Two-Dimensional Cover Problems
by: Cavalar, Bruno P., et al.
Published: (2025)

Spectral Norm, Economical Sieve, and Linear Invariance Testing of Boolean Functions
by: Datta, Swarnalipa, et al.
Published: (2023)

On Approximability of Satisfiable k-CSPs: V
by: Bhangale, Amey, et al.
Published: (2024)

Compilation and Fast Model Counting beyond CNF
by: de Colnet, Alexis, et al.
Published: (2025)

On Approximability of Satisfiable $k$-CSPs: VI
by: Bhangale, Amey, et al.
Published: (2024)

On Approximability of Satisfiable $k$-CSPs: VII
by: Bhangale, Amey, et al.
Published: (2024)

On Approximability of Satisfiable k-CSPs: IV
by: Bhangale, Amey, et al.
Published: (2023)

The Computational Complexity of Satisfiability in State Space Models
by: Alsmann, Eric, et al.
Published: (2025)

Instance complexity of Boolean functions
by: Liu, Alison Hsiang-Hsuan, et al.
Published: (2023)

The Algebraic Cost of a Boolean Sum
by: Orzel, Ian, et al.
Published: (2025)

Boolean Functions with Minimal Spectral Sensitivity
by: Prūsis, Krišjānis, et al.
Published: (2024)

On Boolean PCSPs with Polynomial Threshold Polymorphisms
by: Michno, Katzper
Published: (2025)

Special Coverings of Sets and Boolean Functions
by: Margaryan, Stepan
Published: (2024)

Nearest Neighbor Complexity and Boolean Circuits
by: DiCicco, Mason, et al.
Published: (2024)

Ideal Membership Problem for Boolean Minority and Dual Discriminator
by: Bharathi, Arpitha P., et al.
Published: (2024)

Gateways to Tractability for Satisfiability in Pearl's Causal Hierarchy
by: Ganian, Robert, et al.
Published: (2025)

Boolean PCSPs through the lens of Fourier Analysis
by: Banakh, Demian, et al.
Published: (2026)

Low Degree Local Correction Over the Boolean Cube
by: Amireddy, Prashanth, et al.
Published: (2024)