Some logics used to model "might" and "must" deliberately drop one classical rule: that "A and (B or C)" always means the same as "(A and B) or (A and C)". Dropping this rule, called distributivity, lets these logics treat "the coin might be heads, might be tails, and is heads or tails" as one coherent state of knowledge. It also makes reasoning cheaper. Fundamental logic, a very weak logic with no distributive law, is decidable in polynomial time, while classical modal logics are typically PSPACE-complete. What is missing is the witness. When such a reasoner says an inference fails, the theory says a counterexample exists: a small graph of partial states connected by a "compatible with" relation in which the premises hold and the conclusion does not. No known procedure builds that graph efficiently. The completeness proofs build it from canonical constructions that can be exponentially large or infinite. The only evidence that small graphs exist at all is an exhaustive computer check on lattices of up to 16 elements.
This note proposes to close that gap between knowing a counterexample exists and being able to construct one. The central claim is that the polynomial-time decision procedure for fundamental modal logic can be instrumented to output an explicit certificate for every answer. A valid inference gets a natural-deduction proof. An invalid one gets a finite compatibility frame whose size grows polynomially, and conjecturally quadratically, in the number of subformulas. We would build this procedure, prove its size bound or find where the bound fails, and test it empirically against brute-force and solver-based frame search. We would then extend it to epistemic orthologic, the logic proposed for natural-language epistemic modals.
Background and the gap
This proposal treats non-distributive semantics as the object and the existence-construction gap as the lens. The algorithmic motivation comes from graph theory, where existence proofs have repeatedly been turned into search procedures that output concrete witnesses. The Lovász Local Lemma, a probabilistic argument showing that bad events can all be avoided at once, was made constructive by local search for asymptotically optimal list-edge colouring in Efficiently list-edge coloring multigraphs asymptotically optimally. The Flat Wall Theorem, which guarantees a large grid-like structure inside any graph of large treewidth, received an algorithmic proof in A new proof of the flat wall theorem. Obstructions that certify treewidth were made explicit in Constant Congestion Brambles. We borrow the standard of success from these works: an algorithm that outputs a checkable object whose size is provably bounded. We do not borrow their probabilistic machinery.
The logical side supplies both the objects and the open problem. Holliday's Compatibility and accessibility: Lattice representations for semantics of non-classical and modal logics represents lattices by compatibility frames. A compatibility frame is a set of states $X$ with a reflexive relation $\triangleleft$; a proposition is a set of states that is closed under a derived closure operator, and these closed sets form a lattice. The paper adds an accessibility relation $R$ to interpret necessity. Its notebook experiments show that "economical" frames, meaning frames with fewer states than the lattice has elements, exist for every lattice up to size 16, but the paper gives no general construction. Modal Logic, Fundamentally proves soundness and completeness of fundamental modal logic over frames with a single accessibility relation (Theorems 5.2 and 6.2) and notes polynomial-time decidability. A fundamental non-classical logic gives the propositional base: a Fitch-style natural-deduction system that becomes orthologic when proof by contradiction is added. The Orthologic of Epistemic Modals motivates the application. It shows that orthologic validates the contradictoriness of "it is raining but it might not be" without the classical collapse, and it leaves automated search for satisfying models open.
The nearest algorithmic work is knowledge compilation for classical epistemic logic. Knowledge compilation preprocesses a formula into a form that answers queries quickly. Knowledge Compilation in the Modal Logic S5 shows that Shannon expansion, the case split on a variable that underlies binary decision diagrams, fails in S5. Knowledge Compilation in the Multi-Agent Epistemic Logic Kn obtains single-exponential normal forms for the multi-agent logic $K_n$. Both work over classical logics with Boolean fragments and neither outputs countermodels, so they constrain our design without overlapping with it. Nothing in the file builds certificates for any non-distributive logic.
Core claim
For a sequent $\Gamma \vdash \varphi$ of fundamental modal logic with $n$ distinct subformulas, the proposed procedure runs in polynomial time and returns one of two certificates. If the sequent is valid, it returns a derivation. If not, it returns a frame $(X, \triangleleft, R)$ together with a valuation, both checkable in polynomial time, in which every formula of $\Gamma$ holds at some state where $\varphi$ fails, with
$$|X| = O(n^2).$$
Here $|X|$ is the number of states. The quadratic form is a conjecture, and the reason for it is as follows. Polynomial-time decision for these logics works by saturating judgments about pairs of subformulas. We propose to let each failed pair-judgment, that is, each pair (formula forced true, formula not forced) that saturation cannot close, become one state. Two such states are declared compatible exactly when saturation cannot derive a conflict between them. Accessibility $R$ is read off from the modal rules in the same way. If this construction is sound, the frame is essentially the saturation table read as a graph. That is the sense in which the existence proof becomes a construction.
A second claim follows for finite lattices given explicitly. Taking states to be pairs of irreducible elements, one join-irreducible and one meet-irreducible, should give a polynomial-time construction of an economical frame. This would turn Holliday's size-16 check into a theorem. The exact minimum frame size is a separate question, and we expect it may be NP-hard. We will test that conjecture rather than assume it.
Research Program
The first stage is theoretical. We define the saturation procedure over subformula pairs and prove that it agrees with the known decision procedure. We then prove that the extracted frame satisfies the representation conditions of Modal Logic, Fundamentally: reflexive compatibility, and the interaction axiom $\Diamond \neg a \leq \neg \Box a$ that justifies using a single relation. The main risk is that the closure operator on the extracted frame produces extra fixpoints that break the countermodel. If so, we will characterise which connectives or modal patterns force a larger state space. That negative result is itself a precise description of where the existence-construction gap sits.
The second stage handles lattice-to-frame synthesis. Given a finite lattice, we build the frame from irreducible pairs, prove that the result represents the lattice, and compare its size with the true minimum found by exact search. The third stage extends the extraction to epistemic orthologic. There, symmetric compatibility is required, and Level 0 factual sentences must receive classical treatment, so the extraction must respect the stratification into epistemic levels described in The Orthologic of Epistemic Modals. The file does not state a complexity result for epistemic orthologic. We will therefore report measured scaling rather than claim a bound.
Baselines
The do-nothing reference is a classical S5 reasoner that produces Kripke countermodels. This is the standard possible-worlds semantics in which distributivity holds. It is fast and does output countermodels, but it gives the wrong verdict on the target inferences. It treats the coin-state and Wittgenstein examples as the orthologic paper says a classical treatment must. We run it on the same formula suites and count verdict disagreements against a hand-annotated gold standard drawn from the examples in The Orthologic of Epistemic Modals. Beating it means matching its speed while making zero disagreements on those examples.
The second baseline is canonical-model construction, the countermodel the completeness proofs of Modal Logic, Fundamentally implicitly supply. We implement it for the same fragment. Beating it means producing frames that are polynomially smaller in size, with lower wall-clock time, on identical formulas.
The strongest practical competitor is generic exact search. We encode "a frame with at most $k$ states that refutes the sequent" as a SAT or SMT problem and search upward in $k$. We also run the equivalent brute-force enumeration that underlies Holliday's lattice notebook. We found no reported result on Lacuna for solver-based frame synthesis. The only relevant reported figure is that economical frames exist "for all possible lattices up to size 16" in Compatibility and accessibility. To keep the comparison fair, we give the solver the same machine and a matched per-instance time budget, and we allow it to report its smallest frame found so far. Beating it means that, as input size grows, our procedure keeps answering while the solver times out, and that our frames stay within a small constant factor of the solver's optimum wherever the solver finishes.
Two ablations isolate what the proposal adds. The first removes the compatibility-pruning step and connects every pair of non-conflicting states naively. This tests whether our definition of compatibility is doing real work. The second keeps the decision procedure but drops certificate extraction. This measures how much extraction costs compared with bare decision.
Why not just…?
Why not just use classical modal logic and its well-understood countermodels? Classical logic answers the wrong question. The Orthologic of Epistemic Modals argues that pragmatic explanations cannot account for Wittgenstein sentences staying contradictory when embedded under "suppose". It also argues that the distributive law splits coherent uncertain states. Classical countermodels therefore certify verdicts we consider incorrect. The S5 baseline makes this measurable by counting verdict disagreements.
Why not just hand the problem to a SAT solver? This is a real threat. For small formulas and lattices, the solver will likely find smaller frames than ours, and possibly optimal ones. The proposal offers two things a solver does not: a proven polynomial size bound, and polynomial running time on every input. The scaling experiment settles the matter. If the solver keeps up with our procedure on the largest suites, the practical case weakens to the theorem alone, and we will report that honestly.
Why not just take the canonical model from the completeness proof? Canonical models are built from all maximal consistent sets or all fixpoints, so their size explodes. That explosion is exactly the existence-construction gap. The canonical baseline measures how large the explosion is.
Why not compile formulas into existing epistemic normal forms? Knowledge Compilation in the Modal Logic S5 shows that Shannon expansion already fails in S5. The $K_n$ forms in Knowledge Compilation in the Multi-Agent Epistemic Logic Kn depend on a classical propositional base. Neither produces countermodels, and both assume the classical logic we are rejecting.
Proposed Experiments
We will use four test suites. The first contains all lattices up to size 16, the range covered by Holliday's notebook, extended with randomly generated lattices of 17 to 60 elements. On these, we compare the size of the irreducible-pair frame against solver-found minimum frames. The second is a formula suite for fundamental modal logic: randomly generated sequents of increasing subformula count $n$, stratified by modal depth. On this suite we record validity verdicts, certificate size against $n$, and running time. The third is a linguistic suite built from the Wittgenstein, coin, and disjunctive-might examples of the orthologic paper. The fourth translates the disjunctive-belief variants of the Thief, Corridor, and Grapevine epistemic planning problems into formulas. These are exactly the beliefs excluded by the approach of Planning Over Multi-Agent Epistemic States. That paper reports that total time in Corridor rises from about 1.14s to about 38.80s as belief depth goes from 1 to 3. We cite this only as context for how state-space size grows with depth, not as a comparable baseline, because the tasks differ.
Three checks decide the outcome. First, every certificate must pass an independent checker: a separate implementation of the closure-operator semantics. A single incorrect countermodel falsifies the soundness claim. Second, a log-log fit of frame size against $n$ should have slope near 2. A clearly larger slope would refute the quadratic conjecture and point to the modal patterns responsible. Third, on the largest instances, our procedure should finish while solver-based search exceeds the matched budget, and our frames should stay within a constant factor of the optimum wherever the solver does finish. If the extracted frames turn out to need superpolynomial size, the project changes into a lower-bound result. That outcome would show the existence-construction gap is real for this logic, and it is still worth knowing.
References
- Efficiently list-edge coloring multigraphs asymptotically optimally
- A new proof of the flat wall theorem
- Constant Congestion Brambles
- Compatibility and accessibility: Lattice representations for semantics of non-classical and modal logics
- Modal Logic, Fundamentally
- A Fundamental Non-Classical Logic
- The Orthologic of Epistemic Modals
- Knowledge Compilation in the Modal Logic S5
- Knowledge Compilation in the Multi-Agent Epistemic Logic Kn
- Planning Over Multi-Agent Epistemic States: A Classical Planning Approach