CS Paper Radar

Medvedev Logic is Not Decidable. It is π01 -complete. Who Would Have Guessed?

Pawel Pawlowski

cs.LO math.LO ·submitted 2026-09-10 14:10 UTC · v1
theory

Abstract

This project began as an attempt to prove that Medvedev logic is decidable with the help of generative AI systems. The author (as well as the generative AI systems, or at least they claim to be since I have asked them) was surprised by its eventual conclusion. We prove that Medvedev logic ML, the intermediate logic of finite problems, is Pi-01-complete under computable many-one reductions. Consequently, ML is not recursively enumerable, a fortiori undecidable, and admits no recursively enumerable sound and complete proof calculus. The proof connects the periodic domino problem with intuitionistic formulas through a shared intermediate structure that we call a Wang-Medvedev pair. Such a pair consists of a finite partially ordered set of roles together with demands. Demands define the interaction between roles. A realization labels nonempty subsets of a finite set with these roles, respecting the order and satisfying the demands. We associate a pair with each finite Wang system and show that it has a realization iff the system tiles a finite torus. We then construct an intuitionistic formula that fails on some finite Medvedev frame iff the same pair is realizable. Realizability thus provides the link between periodic tilings and the countermodels.

Closest papers

Nearest neighbours by meaning across the whole index.

Medvedev logic is undecidable

cs.LO math.LO ·2026-09-11 ·Rodrigo Nicolau Almeida, Søren Brinck Knudstorp
similarity 0.68
Abstract · 32 pages; main result obtained via LLM (see methodology section)

We show that Medvedev's logic of finite problems, a well-known superintuitionistic logic, is undecidable. The key method is a reduction from the periodic tiling problem to non-theoremhood in Medvedev's logic. This settles a longstanding open problem. Using similar techniques, but reducing instead to the ordinary tiling problem, we likewise obtain undecidability of Skvortsov's logic of infinite problems, and the fact that the two logics are distinct -- in fact, they are separated by any aperiodic tiling of the plane. Due to the fact that Medvedev's logic figures in so many different areas, these results have implications for several fields -- for example, the study of schematic fragments of logics such as propositional dependence logic, or the study of internal logics of toposes. The core idea and technical work of the undecidability proof were obtained using ChatGPT Sol 5.6, and formally verified in Lean by Claude Opus 5. A detailed methodology section outlines how such results were obtained.

0.28

The Metacomplexity Structure of Search Problems

cs.CC ·2026-11-18 ·Shalev Ben-David, M. H. Ebtehaj
similarity 0.60
Abstract · 48 pages

We study the metacomplexity tasks of refuting an algorithm for a given search problem or refuting a mapping reduction between two search problems. We show that these tasks are deeply related to the structure of the lattice of search problems under mapping reductions: the "refutation of a reduction" task amounts to a certain Heyting-type arrow in this lattice. We then give several structural complexity results about search problems and show they have implications for metacomplexity. First, by relating metacomplexity to a Heyting algebra structure, we are able to translate results from intuitionistic logic into complexity theoretic consequences. For example, the propositional logic identity $x\wedge \neg x=\bot$ translates to the following complexity-theoretic fact: if a search problem $R$ reduces to both $S$ and to the refutation task of $S$, then $R$ is in $\mathsf{FP}$. All such logical identities that hold in intuitionistic logic translate to complexity in a black box way. We find prime ideals of the reducibility lattice of search problems; as a consequence, we show that for any verifiable search problem $S$, either $S$ is in $(\mathsf{FP/poly})_{io}$ or else the refutation task of $S$ is in $(\mathsf{FP/poly})_{io}$. Similarly, either $S$ has infinitely-often heuristic algorithms or else the refutation task of $S$ has infinitely often heuristic algorithms. Finally, we give a structural result that may be of independent interest: any "tamely semantic" class of search problems (one which can be enumerated using a Halting oracle) is characterized by its decidably verifiable hard problems.

0.41

A Kruskal Decision Procedure for Intuitionistic Modal Logic IK4

cs.LO ·2026-08-10 ·Mario Piazza
theory similarity 0.59
Abstract · 24

We prove decidability of Simpson's intuitionistic modal logic IK$ by working directly with cut-free nested proofs. Once the end formula is fixed, only finitely many combinations of input and output formulae can occur at a node, although the modal tree itself remains unbounded. We order these nested sequents by rooted homeomorphic embedding: weakening may add input formulae, while transitivity allows a modal edge to be stretched into a non-empty path. Kruskal's theorem makes rooted homeomorphic embedding a well-quasi-order, but does not by itself make backward application of the rules effective: an inference may still occur inside an arbitrarily large context. The finite-support lemma shows that a minimal predecessor need retain only the positions used by the inference, the images of the chosen basis elements, and the branch points joining them. Together with an effective enumeration of bounded rule instances, this bound makes the minimal predecessors computable. Backward closure from the initial sequents gives an increasing sequence of finitely based upward-closed sets. The sequence eventually stabilises, and its stable value is the set of provable nested sequents. At that point, finitely many cut-free proofs suffice: every other provable nested sequent is obtained from one of them by weakening along an embedding. Their maximum height gives a uniform proof-height bound.

0.33

Two-Variable Logic with Arbitrarily Many Successor Relations

cs.LO ·2026-10-07 ·Jakub Michaliszyn, Piotr Witkowski
theory similarity 0.59
Abstract

We study two-variable first-order logic with a finite, input-dependent number of distinguished successor relations and arbitrary additional unary and binary predicates. Each distinguished relation must be the exact immediate-successor relation of some linear order on the common domain; the orders themselves are not available in the language and may have arbitrary order types. We prove that satisfiability belongs to 2NEXPTIME, uniformly in the number of successors. The proof gives finite certificates for possibly infinite models. A closure operation separates local neighbourhood descriptions, called star types, into those of bounded multiplicity and those that can be realized infinitely often. The bounded part is represented explicitly. Outside it, integer height vectors allow overlapping successor requirements to be matched without creating cycles or unintended identifications. Ordering the resulting path components densely then recovers exact successor relations. Consistent assignments of the additional binary predicates handle witnesses involving the bounded part. The same certificates decide infinite satisfiability in 2NEXPTIME and give a doubly exponential threshold above which a finite model guarantees an infinite model. A doubly exponentially large finite core can be forced with only two successors and unary predicates. For finite models, we prove that satisfiability subject to a bound on the total number of reference adjacencies lost by the other orders is NEXPTIME-complete, even when the budget is encoded in binary and the number of successors is part of the input.

0.49

Discrete Linear Ensemble Logic

cs.LO ·2026-08-11 ·Manfred Droste, Guo-Qiang Zhang
published similarity 0.58
Abstract

We study the discrete point-based fragment of Ensemble Logic $\EL(\Nat)$ over the natural numbers, a logic combining displacement $\varphi_u$, bounded metric modalities $\boldBox_t$ and $\mdiamond_t$ with additive bounds, Boolean connectives, and first-order quantification over $\Nat$. Motivated by the need for a unified symbolic layer for biomedical knowledge with temporal, spatial, genomic, and multimodal metric content, we develop the foundational discrete theory of the formalism. We give syntax and semantics, and prove a forward embedding of $\EL(\Nat)$ over a finite proposition set $\mathcal{P}$ into first-order monadic Presburger arithmetic $\FO(\Nat,<,+;\mathcal{P})$. This embedding yields the analytical upper bounds, while a reduction from nondeterministic two-counter machines with recurring control states proves that satisfiability is $Σ^1_1$-complete and validity is dually $Π^1_1$-complete. Expressively, $\EL(\Nat)$ strictly extends the star-free $ω$-languages and is incomparable with the $ω$-regular languages: it defines the non-$ω$-regular counting language $\{a^mb^mc^md^m\mid m\geq 1\}\cdotΣ^ω$, whereas a delimited parity language remains outside the logic by classical Presburger-arithmetic lower bounds. On the proof-theoretic side, we present a sound Hilbert system $\HEL$ and establish completeness relative to monadic Presburger validity as oracle, noting that completeness relative to plain Presburger arithmetic is impossible.

0.22

Pointwise provable equality and the failure of composition

cs.LO math.LO ·2026-09-22 ·Florian Lengyel
theorycode/data similarity 0.57
Abstract · 11 pages. Exposition condensed and discussion of related work revised; mathematical statements and proofs unchanged. Clarified the roles of …

In their studies of pathologies in recursion categories, Montagna (1989) and Di Paola--Montagna (1991) introduce the algebraic systems $S'$ and $S'_T$, respectively, and claim that they are categories. We show that the proposed composition is not independent of the choice of representatives. For every consistent recursively enumerable extension $T$ of Peano arithmetic ($\mathrm{PA}$), we exhibit two unary programs whose partial functions are provably equal in $T$, separately at each standard input. Composing each after a program that searches for a $T$-proof of contradiction and returns its code yields programs that are not equivalent in this sense. An alternative proof uses the productivity of the complement of the diagonal halting set. Montagna's $S'$ is the case $T=\mathrm{PA}$. More generally, for consistent $T\supseteq\mathrm{PA}$, pointwise provable equality is a composition congruence exactly when $T$ proves every true $Π^0_1$ sentence, in which case it is extensional equality. This completeness condition fails for every consistent recursively enumerable $T\supseteq\mathrm{PA}$ by Gödel's second incompleteness theorem. For every extension $T\supseteq\mathrm{PA}$, the least composition congruence containing pointwise provable equality is extensional equality if $T$ is $Σ^0_1$-sound and the universal relation otherwise.

0.35

A decision procedure for intuitionistic modal logic IS4 (and IK4)

cs.LO ·2026-09-21 ·Marianna Girlando, Roman Kuznets, Sonia Marin, Lutz Straßburger
similarity 0.57
Abstract · corrections of minor technical issues in v1

In this paper, we show that the two intuitionistic modal logics IS4 and IK4 are decidable. We provide a constructive decision procedure, that, given a formula, produces either a proof showing the formula to be valid or a finite countermodel falsifying the formula, thus also proving the finite model property for both logics. The main ingredient of our strategy is the introduction of (possibly unsound) loop rules, which encode repeating behaviour in proof search. This paper fixes a previous mistake in our LICS'23 contribution.

0.33

Non-finite Axiomatizability and Undecidability of $\mathsf{Cheq}$

cs.LO math.LO ·2026-09-30 ·Han Xiao
theory similarity 0.57
Abstract

We prove that $\mathsf{Cheq}$ is not finitely axiomatizable, resolving a longstanding open problem in intermediate and modal logics. We further prove that the undecidability of Medvedev logic implies the undecidability of $\mathsf{Cheq}$.

0.23