Cover Image

Polynomial-time Tractable Problems over the $p$-adic Numbers

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Fehm, Arno, Bodirsky, Manuel
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity Logic F.4.1; F.2.1
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

A Complexity Dichotomy for Temporal Valued Constraint Satisfaction Problems
by: Bodirsky, Manuel, et al.
Published: (2024)

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

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

A Complete Finitary Refinement Type System for Scott-Open Properties
by: Riba, Colin, et al.
Published: (2026)

A Note on the Complexity of the Satisfiability Problem for Graded Modal Logics
by: Kazakov, Yevgeny, et al.
Published: (2009)

Structure-Guided Automated Reasoning
by: Bannach, Max, et al.
Published: (2023)

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

Complexity Classification Transfer for CSPs via Algebraic Products
by: Bodirsky, Manuel, et al.
Published: (2022)

The Complexity of Resilience Problems via Valued Constraint Satisfaction
by: Bodirsky, Manuel, et al.
Published: (2023)

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

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)

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)

Deducibility in the full Lambek calculus with weakening is HAck-complete
by: Greati, Vitor, et al.
Published: (2024)

Hypersequent Calculi Have Ackermannian Complexity
by: Balasubramanian, A. R., et al.
Published: (2026)

A LOCAL View of the Polynomial Hierarchy
by: Reiter, Fabian
Published: (2023)

What If Turing Had Preceded Gödel?
by: Oberhoff, Sebastian
Published: (2024)

On the existence of strong proof complexity generators
by: Krajicek, Jan
Published: (2022)

Constant time testability of first-order logic with modulo counting on finitary graphs
by: Adler, Isolde, et al.
Published: (2026)

Extended Nullstellensatz proof systems
by: Krajicek, Jan
Published: (2023)

Two-Level Type Theory and Applications
by: Annenkov, Danil, et al.
Published: (2017)

Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz
by: Conneryd, Jonas, et al.
Published: (2025)

Punctually Standard and Nonstandard Models of Natural Numbers
by: Bazhenov, Nikolay, et al.
Published: (2026)

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

Set Theory in the Foundation of Math; Internal Classes and External Sets
by: Levin, Leonid A.
Published: (2022)

Data-Complexity of the Two-Variable Fragment with Counting Quantifiers
by: Pratt-Hartmann, Ian
Published: (2008)

On the Complexity of the Numerically Definite Syllogistic and Related Fragments
by: Pratt-Hartmann, Ian
Published: (2007)

A Resolution-Based Interactive Proof System for UNSAT
by: Czerner, Philipp, et al.
Published: (2024)

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

Tractable and Intractable Entailment Problems in Separation Logic with Inductively Defined Predicates
by: Echenim, Mnacho, et al.
Published: (2023)

The General and Finite Satisfiability Problems for PCTL are Undecidable
by: Chodil, Miroslav, et al.
Published: (2024)

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

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

Introducing The Maximum Common Bigraph Problem
by: Burns, Kyle, et al.
Published: (2026)

Computability of the Hahn-Banach Theorem Revisited
by: Brattka, Vasco, et al.
Published: (2026)

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

A correspondence between the time and space complexity
by: Latkin, Ivan V.
Published: (2023)

Expressivity of bisimulation pseudometrics over analytic state spaces
by: Luckhardt, Daniel, et al.
Published: (2025)

Satisfiability for Knowing How over Linear Plans is NP-complete
by: Areces, Carlos, et al.
Published: (2026)