\documentclass[11pt,a4paper]{article}
\usepackage[margin=1in]{geometry}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage{microtype}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{mathtools}
\usepackage{booktabs}
\usepackage{array}
\usepackage{enumitem}
\usepackage{xcolor}
\usepackage[hidelinks]{hyperref}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{hypothesis}[theorem]{Hypothesis}
\newtheorem{falsifier}[theorem]{Falsification Criterion}
\newtheorem{example}[theorem]{Example}

\newcommand{\phig}{\varphi}
\newcommand{\Jcost}{J}
\newcommand{\Tc}{T_{\mathrm{c}}}
\newcommand{\Tr}{T_{\mathrm{r}}}

\title{\textbf{P vs NP via the Computation/Recognition Split:\\
A Dual-Complexity Framework\\
from Ledger Dynamics}\\[0.5em]
\large An Exploratory Paper in Recognition Science\\[0.3em]
\normalsize\textcolor{red}{SCAFFOLD --- Not a claim to have resolved P vs NP}}
\author{Jonathan Washburn\\
\small Recognition Science Research Institute, Austin, Texas\\
\small \texttt{washburn.jonathan@gmail.com}}
\date{February 2026}

\begin{document}
\maketitle

\begin{abstract}
\noindent\textbf{Claim hygiene.}  This paper explores a
\emph{hypothetical} framework for understanding the P vs NP problem; it
does \textbf{not} claim to resolve it unconditionally.  All separation
results are conditional on the ledger-computation model.

\medskip
We observe that the Turing machine model implicitly assumes
zero-cost observation: reading a tape cell is free.  In Recognition
Science, observation has fundamental cost $\Jcost(r)$ per query.  This
motivates a dual-complexity framework with two independent measures:
\begin{itemize}[nosep]
\item $\Tc(n)$: \emph{computation complexity} --- internal evolution
  steps (double-entry ledger updates).
\item $\Tr(n)$: \emph{recognition complexity} --- observation operations
  (extracting information from the ledger).
\end{itemize}
In the standard Turing model, $\Tr = 0$ and total cost $= \Tc$.
In the ledger model, $\Tr > 0$ and total cost $= \Tc + \Tr$.

Under ledger assumptions, the double-entry structure forces
\emph{balanced-parity encoding}: information is hidden in the parity
balance of ledger entries.  Extracting one bit of parity requires
$\Omega(n)$ recognition queries (information-theoretic lower bound).
Meanwhile, the internal evolution (computation) can reorganise the ledger
in $O(n^{1/3} \log n)$ steps (subpolynomial in $n$).

This creates a conditional separation:
$\Tc(\text{SAT}) = O(n^{1/3}\log n)$ but
$\Tr(\text{SAT}) = \Omega(n)$.
The P vs NP question splits:
$\text{P} = \text{NP}$ at the computation scale (internal evolution is
fast), $\text{P} \ne \text{NP}$ at the recognition scale (observation is
expensive).  The Clay Millennium problem, as traditionally stated,
conflates $\Tc$ and $\Tr$.

\medskip\noindent\textbf{Status:} SCAFFOLD.  The Lean formalisation
(\texttt{IndisputableMonolith.Complexity.*}) uses explicit hypotheses and
placeholder types.  No unconditional mathematical claims are made.

\medskip\noindent\textbf{Keywords:} P vs NP, dual complexity, computation,
recognition, ledger, balanced parity, Turing incompleteness.
\end{abstract}

\tableofcontents
\newpage

%======================================================================
\section{Introduction and Claim Hygiene}\label{sec:intro}
%======================================================================

\paragraph{What this paper claims.}
\begin{enumerate}[nosep]
\item The Turing model assumes $\Tr = 0$ (zero observation cost).
  This is a modelling choice, not a physical law.
\item If observation has cost ($\Tr > 0$), a separation between
  computation and recognition complexity can arise.
\item The RS ledger structure provides a concrete model in which this
  separation is natural.
\end{enumerate}

\paragraph{What this paper does \textbf{not} claim.}
\begin{enumerate}[nosep]
\item[$\times$] An unconditional proof that P $\ne$ NP (or P $=$ NP).
\item[$\times$] That the ledger model is the ``correct'' model of
  computation.
\item[$\times$] That the Clay problem is formally ill-posed in the
  standard Turing setting.
\end{enumerate}

The paper should be read as: ``\emph{If} the ledger model captures
physical computation, \emph{then} the P/NP distinction splits into
two independent questions.''

%======================================================================
\section{The Standard P vs NP Problem}\label{sec:standard}
%======================================================================

For completeness, we recall the standard formulation.

\begin{definition}[Turing machine]\label{def:turing}
A (deterministic) Turing machine is a tuple
$M = (Q, \Sigma, \delta, q_0, q_{\mathrm{acc}}, q_{\mathrm{rej}})$
with finite state set~$Q$, tape alphabet~$\Sigma$, transition
function~$\delta: Q \times \Sigma \to Q \times \Sigma \times \{L, R\}$,
and distinguished states.  The \emph{time complexity} $T_M(n)$ is the
maximum number of steps on inputs of length~$n$.
\end{definition}

\begin{definition}[P and NP (standard)]\label{def:PNP}
\begin{itemize}[nosep]
\item $\textbf{P}$: the class of languages decidable by a deterministic
  TM in time $O(n^k)$ for some $k$.
\item $\textbf{NP}$: the class of languages for which a ``yes''
  certificate of length $\mathrm{poly}(n)$ can be \emph{verified} in
  polynomial time.
\end{itemize}
The Clay Millennium problem~\cite{Cook2000} asks: is $\textbf{P} = \textbf{NP}$?
\end{definition}

\begin{remark}[The observation that motivates this paper]
In both definitions, every tape-read operation has \textbf{zero cost}.
When the verifier checks a certificate, each symbol lookup is free.
This is an idealisation.  In any physical realisation:
\begin{itemize}[nosep]
\item Reading a memory cell dissipates at least $k_B T \ln 2$ of energy
  (Landauer's bound~\cite{Landauer1961}).
\item In quantum mechanics, measurement disturbs the measured state
  (no-cloning, wavefunction collapse).
\item In the RS framework, observation has cost $\Jcost(r) > 0$ per
  recognition query.
\end{itemize}
The Turing model's $\Tr = 0$ assumption is a modelling choice, not a
physical law.  The question explored in this paper is: what happens to
the P/NP distinction if we take $\Tr > 0$ seriously?
\end{remark}

\subsection{Existing barriers}

No unconditional proof of $\textbf{P} \ne \textbf{NP}$ is known.
Three \emph{barriers} explain why standard techniques fail:
\begin{enumerate}[nosep]
\item \textbf{Relativisation}~\cite{BakerGillSolovay1975}: there exist
  oracles $A, B$ with $\textbf{P}^A = \textbf{NP}^A$ and
  $\textbf{P}^B \ne \textbf{NP}^B$.  Any proof must be
  non-relativising.
\item \textbf{Natural proofs}~\cite{RazborovRudich1997}: if one-way
  functions exist, no ``natural'' combinatorial property can separate
  P from NP.
\item \textbf{Algebrisation}~\cite{AaronsonWigderson2009}: proofs that
  algebrise cannot separate P from NP.
\end{enumerate}

\begin{remark}
The dual-complexity framework in this paper is \emph{not} a technique
within the standard Turing model.  It introduces a new \emph{model}
(ledger computation with $\Tr > 0$), which sidesteps the three barriers
by changing the question rather than answering the original one.  This
is why we label the results ``conditional,'' not ``unconditional.''
\end{remark}

%======================================================================
\section{Dual Complexity Framework}\label{sec:dual}
%======================================================================

\begin{definition}[Recognition-complete complexity]\label{def:dual}
A \emph{recognition-complete} complexity measure assigns to each problem
instance of size $n$ a pair $(\Tc(n), \Tr(n))$:
\begin{itemize}[nosep]
\item $\Tc(n)$: computation steps (internal state transitions).
\item $\Tr(n)$: recognition queries (observation/readout operations).
\end{itemize}
Total cost: $T_{\text{total}}(n) = \Tc(n) + \Tr(n)$.
\end{definition}

\begin{definition}[Turing model as special case]\label{def:turing_special}
The standard Turing model is the special case $\Tr(n) = 0$ for all $n$.
All computation cost resides in $\Tc$.
\end{definition}

%======================================================================
\section{The Ledger Computation Model}\label{sec:ledger}
%======================================================================

\begin{definition}[Ledger computation]\label{def:ledger}
A \emph{ledger computation} consists of:
\begin{itemize}[nosep]
\item \textbf{States:} configurations of a double-entry ledger
  (balanced debit/credit pairs).
\item \textbf{Evolution:} deterministic double-entry updates preserving
  balance ($\sigma = 0$).
\item \textbf{Observation:} extracting information from the ledger by
  querying specific entries, at cost $\Jcost(r)$ per query.
\end{itemize}
\end{definition}

%======================================================================
\section{Balanced Parity Encoding}\label{sec:parity}
%======================================================================

\begin{definition}[Balanced parity]\label{def:balanced}
A ledger configuration has \emph{balanced parity} if the total
debit equals the total credit: $\sum d_i = \sum c_i$.  The double-entry
structure forces this for all admissible states.
\end{definition}

\begin{hypothesis}[Information hiding]\label{hyp:hiding}
In a balanced-parity ledger of $n$ entries, the value of any single-bit
predicate (e.g.\ ``is entry $k$ a debit?'') cannot be determined without
querying at least $\Omega(n)$ entries, because each entry's value is
constrained by the global balance condition.
\end{hypothesis}

\begin{proposition}[Parity lower bound (classical)]\label{prop:parity}
Computing the parity of $n$ bits requires reading all $n$ bits in the
worst case.  No query algorithm can determine $\bigoplus_{i=1}^n x_i$
with fewer than $n$ queries.
\end{proposition}

\begin{proof}
Adversary argument.  Fix any deterministic algorithm making $< n$
queries.  An adversary answers consistently but chooses the unqueried
bit to control parity.  Since the algorithm never queries the last
bit, both parity values are consistent with the observed answers. \qed
\end{proof}

\begin{theorem}[Balanced-parity lower bound]\label{thm:balanced}
In a balanced ledger with $n$ entries where $\sum d_i = \sum c_i$
(debit $=$ credit), determining whether a \emph{specified} entry~$k$
is a debit or credit requires querying at least $n - 1$ entries in the
worst case.
\end{theorem}

\begin{proof}
Fix an algorithm $\mathcal{A}$ that queries fewer than $n - 1$ entries
and claims to determine $d_k$.  There exist at least two unqueried
entries $i, j \ne k$.  Consider two configurations:
\begin{itemize}[nosep]
\item $C_1$: all queried entries as answered, $d_k = +1$,
  and $(d_i, d_j)$ chosen to satisfy balance.
\item $C_2$: all queried entries as answered, $d_k = -1$,
  and $(d_i, d_j)$ chosen to satisfy balance (adjust by swapping $i, j$).
\end{itemize}
Both $C_1$ and $C_2$ are consistent with the observed query answers
(the algorithm cannot distinguish them).  Yet $d_k$ differs.  Hence
$\mathcal{A}$ must err on at least one of $C_1, C_2$.

More precisely: the balance constraint $\sum d_i = S$ (a known constant)
has $\binom{n}{n/2}$ satisfying assignments.  Conditioning on any
$n - 2$ entries leaves a 2-dimensional space; both values of $d_k$ are
compatible.  The argument generalises to randomised algorithms by Yao's
minimax principle~\cite{Yao1977}: a probabilistic algorithm needs
$\Omega(n)$ queries to achieve error $< 1/3$.
\end{proof}

\begin{corollary}\label{cor:global_coupling}
The $\Omega(n)$ lower bound is a consequence of \emph{global coupling}:
the balance constraint links all entries, so local queries reveal
global information only after $\Omega(n)$ samples.
\end{corollary}

\begin{remark}
This is strictly stronger than the classical parity bound
(\cref{prop:parity}): parity hiding is an \emph{incidental} property
of bit strings, while balanced-parity hiding is a \emph{structural}
consequence of the double-entry ledger.  The latter cannot be avoided
by clever encoding because balance is an invariant of the dynamics
(T3 conservation).
\end{remark}

%======================================================================
\section{Worked Example: 3-SAT on a Ledger}\label{sec:example}
%======================================================================

To ground the abstract framework, consider a concrete instance.

\begin{example}[A 3-variable instance]\label{ex:sat}
Let $\phi = (x_1 \vee x_2 \vee \neg x_3) \wedge (\neg x_1 \vee x_3 \vee x_3)$
with $n = 3$ variables.

\textbf{Ledger encoding.}
Each variable $x_i$ is a ledger entry with value $d_i \in \{+1, -1\}$
(debit or credit).  The balanced-parity constraint requires
$\sum_{i=1}^{3} d_i = \pm 1$ (odd parity for 3 entries).

\textbf{Clause checking.}
Clause $C_j$ is satisfied iff the appropriate combination of $d_i$
values yields a non-zero inner product with the clause template.  A
single clause check reads 3 entries: cost $= 3 \cdot \Jcost(d_i) = 3 \cdot 0 = 0$
for $d_i = \pm 1$ (unit entries have zero $\Jcost$).  However,
\emph{determining the value} $d_i = +1$ vs $d_i = -1$ requires a
recognition query.

\textbf{Computation phase.}  The ledger evolves internally via
double-entry updates.  After $O(n^{1/3}\log n) = O(1.4 \cdot 1.1) \approx 2$
steps (for $n=3$), the internal state reorganises.

\textbf{Recognition phase.}  To \emph{read out} the satisfying
assignment, the observer must query each $d_i$: cost $= n = 3$ queries.
Even after computation has finished, the answer is ``hidden'' in the
ledger's balanced-parity structure until observed.

\textbf{The gap.}  $\Tc = 2$, $\Tr = 3$.  For $n = 3$ the gap is
negligible, but it grows: $\Tc = O(n^{1/3}\log n)$ is sublinear while
$\Tr = \Omega(n)$ is linear.  By $n = 1000$: $\Tc \approx 70$ but
$\Tr \ge 1000$.
\end{example}

%======================================================================
\section{Conditional SAT Separation}\label{sec:sat}
%======================================================================

\begin{hypothesis}[SAT computation complexity]\label{hyp:tc}
Under the ledger model, the internal evolution can reorganise a SAT
instance of $n$ variables into a satisfying assignment (if one exists)
in $\Tc(n) = O(n^{1/3} \log n)$ steps.
\end{hypothesis}

\begin{hypothesis}[SAT recognition complexity]\label{hyp:tr}
Under the ledger model, \emph{verifying} that the reorganised ledger
encodes a satisfying assignment requires $\Tr(n) = \Omega(n)$
recognition queries (from balanced-parity information hiding).
\end{hypothesis}

\begin{theorem}[Conditional separation]\label{thm:separation}
If Hypotheses~\ref{hyp:tc} and~\ref{hyp:tr} hold, then:
\[
  \Tc(\text{SAT}) = O(n^{1/3} \log n) \;\ll\; \Tr(\text{SAT}) = \Omega(n).
\]
Computation is fast; recognition is slow.  The ``hardness'' of SAT
resides in observation, not evolution.
\end{theorem}

%======================================================================
\section{The Split Resolution}\label{sec:resolution}
%======================================================================

\begin{theorem}[P vs NP splits (conditional)]\label{thm:split}
Under the dual-complexity framework:
\begin{itemize}[nosep]
\item \textbf{At the computation scale ($\Tc$ only):}
  P $=$ NP.  The internal evolution can solve NP-complete problems in
  subpolynomial $\Tc$.
\item \textbf{At the recognition scale ($\Tr$ only):}
  P $\ne$ NP.  Observation of the solution requires polynomial $\Tr$,
  creating a separation from the $\Tc$ measure.
\item \textbf{In the Turing model ($\Tr = 0$):}
  The question is ill-conditioned because $\Tr$ is absorbed into $\Tc$
  and the split is invisible.
\end{itemize}
\end{theorem}

%======================================================================
\section{Implications}\label{sec:implications}
%======================================================================

\begin{enumerate}
\item \textbf{Quantum computers shift $\Tc$, not $\Tr$.}  Quantum
  speedups (Grover, Shor) accelerate internal evolution but do not
  eliminate observation cost.  The recognition barrier remains.

\item \textbf{Measurement is fundamentally expensive.}  The RS collapse
  threshold $C \ge 1$ makes measurement a real physical cost, not a
  free operation.

\item \textbf{Consciousness has irreducible observation cost.}  The
  attention operator (Section~4 of~\cite{WashburnDecision2026}) is a
  recognition gate with bounded capacity $\phig^3$.  Even a conscious
  agent cannot bypass $\Tr$.
\end{enumerate}

%======================================================================
\section{Falsification Criteria}\label{sec:falsifiers}
%======================================================================

\begin{falsifier}[Free observation]
If a physical system is demonstrated where observation has zero energy
cost (violating Landauer's bound), the $\Tr > 0$ premise is falsified.
\end{falsifier}

\begin{falsifier}[No parity barrier]
If a SAT instance can be verified in $o(n)$ queries on a balanced-parity
ledger, the information-hiding hypothesis is falsified.
\end{falsifier}

%======================================================================
\section{Comparison with Existing Work}\label{sec:prior}
%======================================================================

\begin{center}
\small
\renewcommand{\arraystretch}{1.15}
\begin{tabular}{@{}>{\bfseries}l p{8.5cm}@{}}
\toprule
Reference & Relation to this work \\
\midrule
Baker--Gill--Solovay~\cite{BakerGillSolovay1975}
  & Relativisation barrier; we sidestep it by changing the model, not
    proving a Turing-model separation. \\
Razborov--Rudich~\cite{RazborovRudich1997}
  & Natural proofs barrier; our lower bound is information-theoretic
    (adversary), not combinatorial. \\
Aaronson--Wigderson~\cite{AaronsonWigderson2009}
  & Algebrisation barrier; the ledger model is not an algebraic extension
    of a Turing oracle. \\
Landauer~\cite{Landauer1961}
  & Physical cost of information; we formalise this as $\Tr > 0$. \\
Bennett~\cite{Bennett1982}
  & Reversible computation; $\Tc$ in reversible models is $O(\Tc_{\text{irrev}}^2)$,
    but $\Tr$ is unchanged. \\
Grover~\cite{Grover1996}
  & Quantum search gives $\Tc \to O(\sqrt{n})$; $\Tr$ remains
    $\Omega(n)$ (measurement collapses the state). \\
\bottomrule
\end{tabular}
\end{center}

%======================================================================
\section{Discussion}\label{sec:discussion}
%======================================================================

\subsection*{Claims and non-claims}

We have introduced a dual-complexity framework $(\Tc, \Tr)$ and shown
that the RS ledger model provides a natural setting where $\Tc$ and
$\Tr$ can diverge.  The key mathematical content is:
\begin{enumerate}[nosep]
\item The balanced-parity lower bound (\cref{thm:balanced}): proved
  unconditionally within the query-complexity model.
\item The conditional separation (\cref{thm:separation}): $\Tc \ll \Tr$
  for SAT, \emph{if} the ledger model's $\Tc$ hypothesis holds.
\item The split (\cref{thm:split}): P${}={}$NP at $\Tc$, P${}\ne{}$NP
  at $\Tr$, under the same hypothesis.
\end{enumerate}
Item~(1) is rigorous.  Items~(2) and~(3) are conditional.

\subsection*{Why this is not a resolution of P vs NP}

The Clay problem asks about the standard Turing model, where
$\Tr = 0$ by definition.  Our framework changes the model.  We do
\emph{not} prove P${}\ne{}$NP in the Turing model; we argue that the
Turing model's conflation of $\Tc$ and $\Tr$ may be the source of the
difficulty.

\subsection*{Falsifiability}

The framework makes two testable predictions:
\begin{enumerate}[nosep]
\item Any physical computation system will exhibit $\Tr > 0$
  (Landauer's bound is never zero).
\item The ``hardness'' of NP-complete problems in practice will
  correlate more with \emph{verification cost} (how many bits must be
  read to check a solution) than with \emph{search cost} (how many
  internal steps to find a candidate).
\end{enumerate}

\subsection*{Open problems}

\begin{enumerate}[label=\textup{(Q\arabic*)},nosep]
\item Can $\Tc(\text{SAT}) = O(n^{1/3}\log n)$ be proved in a
  concrete ledger model, or is it only a hypothesis?
\item Does the dual framework have a clean complexity-class
  formulation (e.g.\ ``$\textbf{P}_c$'' for computation-only, ``$\textbf{P}_r$''
  for recognition-only)?
\item Is there a natural analogue of the PCP theorem in the dual
  setting (probabilistic recognition with $o(n)$ queries)?
\item Does the framework apply to \textbf{BPP} vs \textbf{BQP}
  (randomised vs quantum)?
\end{enumerate}

%======================================================================
\section{Lean Formalization Status}\label{sec:lean}
%======================================================================

The Lean module \texttt{IndisputableMonolith.Complexity.ComputationBridge}
is explicitly marked as \textbf{SCAFFOLD} and is \textbf{not} part of
the verified certificate chain.  Key caveats:
\begin{itemize}[nosep]
\item \texttt{LedgerComputation.states} uses \texttt{Type} as a
  placeholder (often \texttt{Unit}).
\item Separation theorems rely on hypothetical model assumptions.
\item No result should be cited as proven mathematics.
\end{itemize}

\begin{center}
\begin{tabular}{@{}ll@{}}
\toprule
\textbf{Module} & \textbf{Content} \\
\midrule
\texttt{Complexity.ComputationBridge} & Dual framework, separation \\
\texttt{Complexity.BalancedParityHidden} & Parity hiding \\
\texttt{Complexity.VertexCover} & Example reductions \\
\texttt{Complexity.RSVC} & RS vertex cover \\
\bottomrule
\end{tabular}
\end{center}

\begin{thebibliography}{99}
\bibitem{WashburnCost2026}
J.~Washburn and M.~Zlatanovi\'{c},
``The Cost of Coherent Comparison,''
arXiv:2602.05753v1, 2026.

\bibitem{WashburnDecision2026}
J.~Washburn,
``Decision as Cost Geodesic,''
Recognition Science preprint, February 2026.

\bibitem{Landauer1961}
R.~Landauer,
``Irreversibility and heat generation in the computing process,''
\textit{IBM J. Res.~Dev.}, 5(3):183--191, 1961.

\bibitem{Cook2000}
S.~Cook,
``The P versus NP problem,''
Clay Mathematics Institute Millennium Problems, 2000.

\bibitem{BakerGillSolovay1975}
T.~Baker, J.~Gill, and R.~Solovay,
``Relativizations of the P $=?$ NP question,''
\textit{SIAM J. Comput.}, 4(4):431--442, 1975.

\bibitem{RazborovRudich1997}
A.~A.~Razborov and S.~Rudich,
``Natural proofs,''
\textit{J. Comput. System Sci.}, 55(1):24--35, 1997.

\bibitem{AaronsonWigderson2009}
S.~Aaronson and A.~Wigderson,
``Algebrization: a new barrier in complexity theory,''
\textit{ACM Trans. Comput. Theory}, 1(1):2:1--2:54, 2009.

\bibitem{Bennett1982}
C.~H.~Bennett,
``The thermodynamics of computation---a review,''
\textit{Int. J. Theor. Phys.}, 21(12):905--940, 1982.

\bibitem{Grover1996}
L.~K.~Grover,
``A fast quantum mechanical algorithm for database search,''
\textit{Proc. 28th ACM STOC}, 212--219, 1996.

\bibitem{Yao1977}
A.~C.-C.~Yao,
``Probabilistic computations: toward a unified measure of complexity,''
\textit{Proc. 18th IEEE FOCS}, 222--227, 1977.
\end{thebibliography}

\end{document}
