Image de couverture de livre

On the Satisfaction Probabilities of $k$-CNF Formulas

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteur principal:	Tantau, Till
Format:	Preprint
Publié:	2022
Sujets:	Computational Complexity Logic in Computer Science F.1.3; F.4.1; F.2.2
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs
par: de Rezende, Susanna F., et autres
Publié: (2019)

On bounded depth proofs for Tseitin formulas on the grid; revisited
par: Håstad, Johan, et autres
Publié: (2022)

Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz
par: Conneryd, Jonas, et autres
Publié: (2025)

Superpolynomial Length Lower Bounds for Tree-Like Semantic Proof Systems with Bounded Line Size
par: de Rezende, Susanna F., et autres
Publié: (2026)

Clique Is Hard on Average for Sherali-Adams with Bounded Coefficients
par: de Rezende, Susanna F., et autres
Publié: (2024)

Supercritical Tradeoffs for Monotone Circuits
par: Göös, Mika, et autres
Publié: (2024)

Notes on CSPs and Polymorphisms
par: Brady, Zarathustra
Publié: (2022)

A Note on the Complexity of the Satisfiability Problem for Graded Modal Logics
par: Kazakov, Yevgeny, et autres
Publié: (2009)

Deducibility in the full Lambek calculus with weakening is HAck-complete
par: Greati, Vitor, et autres
Publié: (2024)

Hypersequent Calculi Have Ackermannian Complexity
par: Balasubramanian, A. R., et autres
Publié: (2026)

Constant time testability of first-order logic with modulo counting on finitary graphs
par: Adler, Isolde, et autres
Publié: (2026)

Polynomial-time Tractable Problems over the $p$-adic Numbers
par: Fehm, Arno, et autres
Publié: (2025)

A Complexity Dichotomy for Temporal Valued Constraint Satisfaction Problems
par: Bodirsky, Manuel, et autres
Publié: (2024)

Structure-Guided Automated Reasoning
par: Bannach, Max, et autres
Publié: (2023)

A LOCAL View of the Polynomial Hierarchy
par: Reiter, Fabian
Publié: (2023)

A Complete Finitary Refinement Type System for Scott-Open Properties
par: Riba, Colin, et autres
Publié: (2026)

Introducing The Maximum Common Bigraph Problem
par: Burns, Kyle, et autres
Publié: (2026)

Semantics out of context: nominal absolute denotations for first-order logic and computation
par: Gabbay, Murdoch J.
Publié: (2013)

Imperative process algebra and models of computation
par: Middelburg, C. A.
Publié: (2022)

Infinitary Refinement Types for Temporal Properties in Scott Domains
par: Riba, Colin, et autres
Publié: (2025)

Constructibility and the P versus NP problem
par: Hole, Arne
Publié: (2024)

On the Descriptive Complexity of Groups without Abelian Normal Subgroups
par: Grochow, Joshua A., et autres
Publié: (2022)

Turing machines deciders, part I
par: The bbchallenge Collaboration, et autres
Publié: (2025)

Failure of the strong feasible disjunction property
par: Krajicek, Jan
Publié: (2026)

Interpreting De Finetti's theorem in the Category of Integrable Cones (long version)
par: Raphaëlle, Crubillé
Publié: (2026)

One Energy Game for the Spectrum between Branching Bisimilarity and Weak Trace Semantics
par: Bisping, Benjamin, et autres
Publié: (2024)

A Fibrational Perspective on Differential Linear Logic
par: Koleilat, Jad
Publié: (2026)

On Higher-Order Probabilistic Verification via the Weighted Relational Model of Linear Logic
par: Lago, Ugo Dal, et autres
Publié: (2026)

Relational Dualities and Bisimulation
par: Kozicki, Piotr, et autres
Publié: (2026)

A correspondence between the time and space complexity
par: Latkin, Ivan V.
Publié: (2023)

Formally Verifying the Safety of Pipelined Moonshot Consensus Protocol
par: Praveen, M., et autres
Publié: (2024)

On the Complexity of Determinations
par: Hellerstein, Joseph M.
Publié: (2026)

Hardness of busy beaver value BB(15)
par: Stérin, Tristan, et autres
Publié: (2021)

The Fluted Fragment with Transitive Relations
par: Pratt-Hartmann, Ian, et autres
Publié: (2020)

Unravelling Abstract Cyclic Proofs into Proofs by Induction
par: Grotenhuis, Lide, et autres
Publié: (2026)

A Proof-Theoretic Approach to the Semantics of Classical Linear Logic
par: Barroso-Nascimento, Victor, et autres
Publié: (2025)

Logics for the Relational Syllogistic
par: Pratt-Hartmann, Ian, et autres
Publié: (2008)

A Note on the NP-Hardness of PARTITION Via First-Order Projections
par: Iturralde, Paúl Risco
Publié: (2025)

New Bounds for the Ideal Proof System in Positive Characteristic
par: Behera, Amik Raj, et autres
Publié: (2025)

Automating the Derivation of Unification Algorithms: A Case Study in Deductive Program Synthesis
par: Waldinger, Richard
Publié: (2025)