Cover Image

SAT problem and Limit of Solomonoff's inductive reasoning theory

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Pan, Feng
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity Logic in Computer Science F.1.3
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

On the Counting Complexity of the Skolem Problem
by: Jindal, Gorav, et al.
Published: (2024)

Imperative process algebra and models of computation
by: Middelburg, C. A.
Published: (2022)

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

Symmetric Arithmetic Circuits
by: Dawar, Anuj, et al.
Published: (2020)

Lower Bounds for Symmetric Circuits for the Determinant
by: Dawar, Anuj, et al.
Published: (2021)

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

A SAT-based Approach for Specification, Analysis, and Justification of Reductions between NP-complete Problems
by: Janičić, Predrag
Published: (2025)

Finitely (In)tractable Promise Constraint Satisfaction Problems
by: Asimi, Kristina, et al.
Published: (2020)

Constructibility and the P versus NP problem
by: Hole, Arne
Published: (2024)

An MDL-Style Cost Functional KC, Distribution-Preserving Reductions ($A2^d$), and an $AC^0$+log Lower Bound for 3SAT via Balanced 3XOR
by: Lela, Marko
Published: (2025)

On the Computational Power of Extensional ESO
by: Bodirsky, Manuel, et al.
Published: (2025)

Hereditary First-Order Logic: the tractable quantifier prefix classes
by: Bodirsky, Manuel, et al.
Published: (2024)

Notes on CSPs and Polymorphisms
by: Brady, Zarathustra
Published: (2022)

Failure of the strong feasible disjunction property
by: Krajicek, Jan
Published: (2026)

Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs
by: de Rezende, Susanna F., et al.
Published: (2019)

Predicative Ordinal Recursion on the Constructive Veblen Hierarchy
by: Tabatabai, Amirhossein Akbar, et al.
Published: (2025)

New Bounds for the Ideal Proof System in Positive Characteristic
by: Behera, Amik Raj, et al.
Published: (2025)

The Solver's Paradox in Formal Problem Spaces
by: Rosko, Milan
Published: (2025)

Reasoning about distributive laws in a concurrent refinement algebra
by: Meinicke, Larissa A., et al.
Published: (2024)

Restructuring a concurrent refinement algebra
by: Hayes, Ian J., et al.
Published: (2024)

Insignificant Choice Polynomial Time: A Logic Capturing PTIME
by: Schewe, Klaus-Dieter
Published: (2020)

On the Length of Strongly Monotone Descending Chains over $\mathbb{N}^d$
by: Schmitz, Sylvain, et al.
Published: (2023)

Disjunctive Complexity
by: Ivanov, Nikita, et al.
Published: (2025)

L is different from NP
by: Montoya, J. Andres
Published: (2024)

Separation Results for Constant-Depth and Multilinear Ideal Proof Systems
by: Behera, Amik Raj, et al.
Published: (2026)

Completing the Complexity Classification of 2-Solo Chess: Knights and Kings are Hard
by: Kühn, Kolja, et al.
Published: (2026)

Gaps, Ambiguity, and Establishing Complexity-Class Containments via Iterative Constant-Setting
by: Hemaspaandra, Lane A., et al.
Published: (2021)

Hausdorff Reductions and the Exponential Hierarchies
by: Malizia, Enrico
Published: (2024)

Understanding Robust Catalytic Computing
by: Koucký, Michal, et al.
Published: (2026)

The Complexity of Strategic Behavior in Primary Elections
by: Cleveland, Colin, et al.
Published: (2026)

Complexity of Nonassociative Lambek Calculus with classical logic
by: Płaczek, Paweł
Published: (2024)

Truth Predicate of Inductive Definitions and Logical Complexity of Infinite-Descent Proofs
by: Ito, Sohei, et al.
Published: (2026)

Hardness of busy beaver value BB(15)
by: Stérin, Tristan, et al.
Published: (2021)

A Theory for Probabilistic Polynomial-Time Reasoning
by: Chen, Lijie, et al.
Published: (2026)

Catalytic Computing and Register Programs Beyond Log-Depth
by: Alekseev, Yaroslav, et al.
Published: (2025)

A point to set principle for finite-state dimension
by: Mayordomo, Elvira
Published: (2022)

Reachability with Restricted Reactions in Inhibitory Chemical Reaction Networks
by: Bajaj, Divya, et al.
Published: (2026)

Towards New Characterizations of Small Circuit Classes via Discrete Ordinary Differential Equations
by: Antonelli, Melissa, et al.
Published: (2025)

Complexity Classes Arising from Circuits over Finite Algebraic Structures
by: Kawałek, Piotr, et al.
Published: (2026)

Logics for the Relational Syllogistic
by: Pratt-Hartmann, Ian, et al.
Published: (2008)