The Observer World: A Cryptographic Extension of Impagliazzo’s Five Worlds Fabio Francesco Gabriele Buono Independent Researcher
arXiv:2606.27139v1 [cs.CR] 25 Jun 2026
ORCID: 0009-0004-9199-2793
2026 Abstract Impagliazzo’s five worlds classify computational assumptions along a single axis, the existence of cryptographic primitives. All five worlds implicitly assume that every party, including the adversary, observes the full input, that the observer is always O⊤ . This assumption is so natural that it is never stated. This work makes it explicit and relaxes it by introducing a second, orthogonal axis, the observational axis, defined by the observer hierarchy of [9]. Relaxing the assumption reveals structural phenomena, such as the collapse POprof = NPOprof ⊊ P, that the five-world framework cannot express. We prove that this collapse holds unconditionally in all five worlds, showing that observational blindness and computational hardness are independent. We define the Observer World WO , classify all world-observer pairs, identify the labeled cells (a)–(d), and introduce a parametric family WOε modelling partial violations of observational invariants. The framework also interfaces with physical information limits, including thermodynamic, quantum, and cosmological bounds.
Contents 1 Introduction
2
2 Preliminaries: canonical observers
3
3 The five worlds and their silent assumption
5
4 The world-observer table 4.1 The table . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 The labeled cells (a)–(d) . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6 7 7
5 The Observer World: a sixth landscape
10
6 Observer worlds with broken invariants 6.1 Three cases of invariant violation . . . . . . . . . . . . . . . . . . . . . . . 6.2 The parametric family WOε . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.3 The most informationally rich cell . . . . . . . . . . . . . . . . . . . . . . .
11 12 13 14
1
7 Physical instantiation of the Observer World 7.1 Adaptive observers, oracles, and the cost of observation . . . . . . . . . . . 7.2 Quantum measurement as an observational transition . . . . . . . . . . . . 7.3 The cosmological bit budget and the physical ceiling of the observational hierarchy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15 15 16
8 Conclusion
18
A Proof of Lemma 5.3
19
B Profile preimage: correctness and complexity
20
C Cosmological calculations and alternative metrics C.1 Cosmological bit budget . . . . . . . . . . . . . . . . . . . . . . . . . . . . C.2 Alternative metrics for ε . . . . . . . . . . . . . . . . . . . . . . . . . . . . C.3 Landauer cost and reversible computation . . . . . . . . . . . . . . . . . .
20 20 21 21
1
16
Introduction
Impagliazzo’s five worlds [16] provide the most influential framework for reasoning about the gap between average-case and worst-case complexity, and about the foundations of cryptography. The five worlds Algorithmica, Heuristica, Pessiland, Minicrypt, Cryptomania are defined by progressively stronger assumptions about the existence of computational hardness, from a world where P = NP to a world where public-key cryptography is possible. Every one of the five worlds makes an implicit assumption that has not been made explicit in the five-world framework: that every party, including the adversary, has complete access to the input. In the language of [9], all five worlds assume that the observer is always O⊤ , the identity function on strings. This assumption is so natural in the computational setting that it is never stated. This paper makes it explicit and relaxes it. The observer theory of [9] introduces a partial order on functions O : Σ∗ → S that map inputs to observations, and proves that when the observer is structurally constrained (i.e. O ≺ O⊤ ), the class of languages decidable under O depends on O alone and not on the nondeterministic power of the machine. In particular, the structural collapse POprof = NPOprof ⊊ P holds unconditionally [9, Propositions 8.3–8.4]: it is not a resolution of P vs NP, but evidence that the distinction between computational hardness and structural blindness is real and independent of any computational assumption. Since this result is unconditional, it holds in all five worlds simultaneously. The five worlds do not have the vocabulary to express it: they parametrise the computational axis but leave the observational axis fixed at O⊤ . In this sense the five worlds do not suffice: they describe variations along a line, while the observational axis exists orthogonally, and its structure is invisible from within any of the five worlds.
2
Cryptographic motivation. In every cryptographic security argument, the adversary sees a ciphertext. The five worlds model computational power but say nothing about what the adversary sees: they implicitly assume O⊤ . The observational axis makes this explicit. Each labeled cell (a)–(d) of the world-observer table identifies a cryptographic phenomenon that the five-world framework cannot express: the observational collapse below the P/NP gap in every world including Algorithmica (cell (a)), the non-additivity of computational hardness and observational blindness (cell (b)), a structural lower bound on one-way functions (cell (c)), and perfect secrecy as O⊥ -blindness on the plaintext (cell (d)). Main contributions. (i) We prove that the structural collapse POprof = NPOprof ⊊ P holds unconditionally in all five worlds simultaneously (Proposition 3.3), and classify the world-observer table, identifying four cells (a)–(d) that each witness a cryptographic phenomenon invisible to the five-world framework (Section 4). (ii) We define the Observer World WO formally as a sixth landscape (Definition 5.1) and prove it is not reducible to any of the five worlds (Proposition 5.4, Section 5). (iii) We introduce the parametric family WOε with invariant violation parameter ε ∈ [0, 1], modelling worlds in which an adversary partially circumvents observational blindness, and identify the most informationally rich cell: Pessiland × Oprof × ε > 0 (Section 6). (iv) We identify connections between the Observer World framework and physical information limits, thermodynamic, quantum, and cosmological, and state precise open problems formalising each connection (Section 7). Limitations. The author is a computer scientist, not a physicist. The physical connections of Section 7 are stated as open problems and conjectures, not theorems; no physical conclusions are claimed beyond what the mathematical framework directly implies. All machines in this paper are standard multi-tape deterministic or nondeterministic Turing machines over {0, 1}∗ ; the observer is a fixed preprocessing map applied before any machine computation begins (see Remark 2.1). The parametric family WOε (Section 6.2) requires an information metric whose precise formulation is an open direction (Section 7.1, Open Problem 7.4).
2
Preliminaries: canonical observers
We recall the definitions and results from [9] used throughout this paper. All machines are standard multi-tape Turing machines. An observer O : Σ∗ → S is a fixed total function applied once to the input before any machine computation begins; it does not interact with the machine and does not extend the computational model. Remark 2.1 (Machine model). PO consists of languages decidable in time polynomial in |enc(O(x))| by a deterministic TM receiving enc(O(x)) as its entire input, where enc : S → {0, 1}∗ is a fixed canonical injective encoding. NPO is defined analogously with a nondeterministic TM and a polynomial-length certificate. For O = O⊤ these reduce to standard P and NP [9, Definition 8.1 and Proposition 8.2(i)]. The observer only 3
reduces available information and never increases computational power [9, Remark after Definition 8.1]. Throughout this paper we identify O(x) with enc(O(x)) and write, e.g., “the TM receives O(x)” as shorthand for “the TM receives enc(O(x))”; all complexity bounds are in terms of |enc(O(x))|. Definition 2.2 (Canonical observers [9, Definition 4.1]). Let Σ = {0, 1} (see Remark 2.3). The canonical observers are: (i) O⊥ : Σ∗ → {⋆}, O⊥ (x) = ⋆ for all x. Map: constant map. Invariant: discards all information. Decidable class: L(O⊥ ) = {∅, Σ∗ } by [9, Proposition 8.2(ii)]. (ii) Olen : Σ∗ → N, Olen (x) = |x|. Map: string length. Invariant: length-determined languages. Decidable class: all L with x ∈ L ⇐⇒ |x| ∈ I for some I ⊆ N. (iii) Opar : Σ∗ → {0, 1}2 , Opar (x) = (|x|0 mod 2, |x|1 mod 2). Map: symbol-count parities. Invariant: parity of each symbol count. Decidable class: all L determined by symbolcount parities. (iv) Oprof : Σ∗ → N2 , Oprof (x) = (|x|0 , |x|1 ) (the profile of x). Map: symbol counts. Invariant: permutation-closure. Decidable class: all permutation-closed languages [9, Theorem 2.1]. (v) Ok : Σ∗ → P(Σ≤k ), where Ok (x) is the set of subsequences of x of length ≤ k (k ≥ 1). Map: k-subsequence set. Invariant: k-piecewise testability. Decidable class: all k-piecewise testable languages (Simon’s hierarchy [9, Section 5]). (vi) O⊤ : Σ∗ → Σ∗ , O⊤ (x) = x. Map: identity. Invariant: none (full information). Decidable class: all languages. Remark 2.3 (Alphabet convention). Definition 2.2 uses Σ = {0, 1} for concreteness. For a general k-symbol alphabet Σ = {a0 , . . . , ak−1 }, replace (|x|0 , |x|1 ) with (|x|a0 , . . . , |x|ak−1 ) ∈ Nk . All order relations and separation witnesses carry over unchanged [9, Remark after Definition 4.1]. The following table summarises the canonical observers.
Observer
Map O(x)
Key invariant
Example L ∈ L(O)
PO = NPO ?
O⊥
⋆
all
∅
yes (trivially)
Olen
|x|
length
{x | |x| even}
open
Opar
parities of counts
symbol parities
{x | |x|1 ≡ 0}
open
Oprof
(|x|0 , |x|1 )
perm.-closure
{x | |x|0 = |x|1 }
yes (structurally)
Ok
k-subsequence set
k-p.t.
{x | 01 ⊑ x}
open
O⊤
x
none
0∗ 1∗
open (P vs NP)
The partial order ⪯ on observers is defined by [9, Definition 4.2]: O1 ⪯ O2 if there exists a function f with O1 = f ◦ O2 . The complete order relations among the canonical observers
4
are: O⊥ ≺ Olen ≺ Oprof ≺ O⊤ , O⊥ ≺ Opar ≺ Oprof ≺ O⊤ , O⊥ ≺ O1 ≺ O2 ≺ · · · ≺ O⊤ , with Olen and Opar incomparable, and Oprof incomparable with every Ok [9, Propositions 3– 5]. A language L ⊆ Σ∗ is O-saturated (Definition 3.2 of [9], also called O-invariant) if O(x) = O(y) implies x ∈ L ⇐⇒ y ∈ L, where we write x ∼O y to denote the equivalence relation O(x) = O(y). Equivalently, L is O-saturated if it is a union of ∼O -equivalence classes, or if membership in L is determined entirely by O(x). We use both terms interchangeably throughout the paper.
3
The five worlds and their silent assumption
We recall the five worlds of Impagliazzo [16] and make their shared implicit assumption explicit. Definition 3.1 (Impagliazzo’s five worlds [16]). lem in NP is solvable in polynomial time.
(i) Algorithmica: P = NP. Every prob-
(ii) Heuristica: P ̸= NP but no NP problem is hard on average: every NP problem has a polynomial-time algorithm that succeeds on all but a negligible fraction of instances under any efficiently samplable distribution. (iii) Pessiland: NP problems are hard on average, but one-way functions do not exist: no function is hard to invert on average. (iv) Minicrypt: one-way functions exist, but public-key cryptography does not: no keyexchange protocol is secure against a computationally bounded adversary. (v) Cryptomania: public-key cryptography exists: there exist functions that are easy to compute but hard to invert even given additional public information (trapdoor one-way functions). Remark 3.2 (The silent assumption). In every world of Definition 3.1, every machine, including the adversary, receives the complete input x. In the language of [9], the observer is always O⊤ : x 7→ x. This assumption is never stated in the five-world framework because it is universal and no party is ever observationally constrained. The five worlds vary the computational assumption (what is hard) but not the observational assumption (what is visible). Proposition 3.3 (The observational collapse is world-independent). In every world Wi of Definition 3.1, the following holds unconditionally: POprof = NPOprof ⊊ P. Proof. By [9, Propositions 8.3 and 8.4], this holds with no assumption on P vs NP and with no cryptographic assumption. Since the five worlds are defined by computational 5
and cryptographic assumptions, and the collapse is independent of all such assumptions, it holds in every world of Definition 3.1. We now sketch why the collapse holds. Any language in POprof has membership determined solely by Oprof (x) = (|x|0 , |x|1 ). A TM under Oprof receives Oprof (x) as its entire input, a string of length O(log |x|). Any nondeterministic certificate must also be a function of this input alone; it cannot depend on x itself (which the machine does not receive). Hence a nondeterministic TM under Oprof decides exactly the same languages as a deterministic one: POprof = NPOprof . The language L0 = 0∗ 1∗ is in P (one linear scan) but not Oprof -decidable: Oprof (01) = Oprof (10) = (1, 1) while 01 ∈ L0 and 10 ∈ / L0 . Hence POprof ⊊ P. Full proof in [9, Propositions 8.3–8.4]. Remark 3.4 (What Proposition 3.3 says). Proposition 3.3 does not say that P = NP holds in all five worlds: it says that a different collapse, one that places POprof strictly below P in the language containment order, due to structural blindness rather than computational coincidence, holds regardless of where we are in the five-world landscape. The five worlds cannot distinguish between a problem that is computationally hard and a problem that is not well-posed for a given observer; Proposition 3.3 shows that these two phenomena are genuinely independent.
4
The world-observer table
We construct the table of all pairs (Wi , O) where Wi is one of the five worlds and O is a canonical observer of [9]. We first formalise the notions of a labeled cell and cell reduction. Definition 4.1 (Non-trivial cell). A cell (Wi , O) of the world-observer table is non-trivial if there exists a language L ∈ PO⊤ \ PO , i.e. if the observational constraint strictly reduces the class of decidable languages. A cell is trivial if PO = NPO = {∅, Σ∗ }, which holds whenever O ⪯ O⊥ [9, Proposition 8.2(ii)]. Note. We call cells (a)–(d) the labeled cells of the table: they are the cells singled out for individual analysis below. Cells (a)–(c) are non-trivial in the formal sense above. Cell (d) (Cryptomania × O⊥ ) is formally trivial (PO⊥ = {∅, Σ∗ }), but is labelled separately in the table because the world Cryptomania contains public-key primitives that create a cryptographically meaningful contrast with the classical cell (Cryptomania, O⊤ ); this distinction is invisible to the formal condition above and is explained in the legend below. Definition 4.2 (Cell reduction). We say cell (Wi , O) many-one reduces to (Wj , O′ ) if there exists a polynomial-time computable map T : Σ∗ → Σ∗ such that for every language L decidable in (Wi , O), there exists a language L′ decidable in (Wj , O′ ) with x ∈ L ⇐⇒ T (x) ∈ L′ for all x, and T preserves observational transcripts: O(x) = O′ (T (x)) for all x. Cell reductions are not used in the proofs of this paper; the definition is included to make precise the sense in which cells are independent that is implicit in Proposition 5.4.
6
4.1
The table O⊥
Olen /Opar
Oprof
Ok
O⊤
Algorithmica
trivial
trivial
(a)
standard
classical
Heuristica
trivial
trivial
(a)
standard
classical
Pessiland
trivial
trivial
(b)
standard
classical
Minicrypt
trivial
trivial
(c)
standard
classical
Cryptomania
(d)
trivial
(a)
standard
classical
Legend. Trivial: PO = NPO = {∅, Σ∗ } by [9, Proposition 8.2(ii)]; computational assumptions are irrelevant. Standard: Simon’s hierarchy applies; see [9, Section 5]. Classical: PO⊤ = P and NPO⊤ = NP; the standard five-world analysis applies [16]. Cells (a)–(c) are non-trivial in the sense of Definition 4.1 and are treated in Section 4.2. Cell (d) (Cryptomania × O⊥ ) is formally trivial by Definition 4.1 but is labelled separately because, as explained in the note within Definition 4.1 and below, the world Cryptomania creates a cryptographically distinct situation for an O⊥ -blind adversary. All other O⊥ cells are listed as trivial: they share the structural property PO⊥ = {∅, Σ∗ } and their computational world creates no analogous contrast. The cell (Cryptomania, O⊥ ) is the sole O⊥ entry worth distinguishing: in Cryptomania, an adversary with O⊤ could exploit public-key primitives, while one with O⊥ cannot even pose the question of which plaintext was encrypted. It is this contrast, absent in all other worlds, that motivates its separate label.
4.2
The labeled cells (a)–(d)
Proposition 4.3 (Cell (a): any world × Oprof ). In every world Wi : POprof = NPOprof ⊊ PO⊤ = P. If additionally P ̸= NP (which is assumed in all worlds except Algorithmica): NPOprof = POprof ⊊ P ⊊ NP. The observational collapse occurs strictly below the P/NP gap, on the opposite side from NP. Proof. Unconditional part: Proposition 3.3. Conditional part: combining with P ⊊ NP under the assumption P ̸= NP. Toy example for cell (a). Let L = {x ∈ {0, 1}∗ | x1 = 1} (strings whose first symbol is 1). For any x, x′ with Oprof (x) = Oprof (x′ ) we can have x1 = 1 and x′1 = 0 (e.g. x = 10, x′ = 01, both with profile (1, 1)). Hence L is not Oprof -decidable. However, L ∈ P (read the first symbol in O(1) time). This witnesses POprof ⊊ P independently of any of the five worlds. Remark 4.4. Cell (a) is the most important labeled cell. It shows that even in Algorithmica, where P = NP, the observational collapse POprof ⊊ P persists. The collapse is not cancelled by the strongest possible computational assumption. The observational and computational axes are orthogonal. 7
Proposition 4.5 (Cell (b): Pessiland × Oprof ). In Pessiland: (i) NP problems are hard on average, but no one-way function exists. (ii) An adversary with observer Oprof cannot pose any problem that depends on the ordering of input symbols: such problems are not Oprof -saturated and are not wellformed in the adversary’s observation space. (iii) The hardness in Pessiland and the blindness of Oprof interact non-additively: problems that are hard on average in Pessiland may be problems that the Oprof adversary cannot even recognise as distinct from trivial ones. (iv) There is no cryptographic security in Pessiland (no one-way functions), but the adversary with Oprof faces a different limitation: structural blindness to ordering. These two limitations are independent; neither implies the other. Proof. Parts (i) and (iv): by definition of Pessiland [16]. Part (ii): by [9, Definition 3.2 and Theorem 2.1], a language is decidable under Oprof if and only if it is permutation-closed; languages depending on ordering are not permutation-closed and hence not Oprof -decidable, regardless of computational power. Part (iii): the hardness of NP problems in Pessiland is a property of the problem as seen by an O⊤ adversary. An Oprof adversary does not see the same problem: orderingdependent difficulty is invisible to it. The two phenomena apply to different parts of the problem landscape and do not combine additively. Toy example for cell (b). The following example illustrates the independence between observational blindness and average-case hardness, not their co-occurrence. Consider the problem: given x ∈ {0, 1}∗ , determine whether x is the lexicographically sorted version of its symbols (all 0s precede all 1s). This problem is in P (one linear scan), not NP-hard, and not hard on average. Nevertheless, an Oprof adversary sees only (|x|0 , |x|1 ) and cannot distinguish 0a 1b from any other string with the same profile; the problem is therefore not Oprof -decidable. This shows that ordering-dependence and Oprof -blindness are independent of the computational difficulty of the problem: a problem can be easy (in P), orderingdependent, and Oprof -invisible simultaneously. The same independence holds for NP-hard ordering-dependent problems in Pessiland: their hardness is a property relative to O⊤ , not a property that Oprof can detect. Lemma 4.6 (Profile preimage construction). Given a profile π = (c0 , . . . , ck−1 ) ∈ Nk with P ′ ∗ ′ n = k−1 i=0 ci , Algorithm 1 constructs a string x ∈ Σ with Oprof (x ) = π in time O(n). Full proof in Appendix B. Algorithm 1 ConstructFromProfile Require: Profile π = (c0 , . . . , ck−1 ) ∈ Nk Ensure: String x′ with Oprof (x′ ) = π 1: x′ ← ε 2: for i = 0 to k − 1 do 3: Append ci copies of symbol ai to x′ 4: end for 5: return x′
8
Proposition 4.7 (Cell (c): Minicrypt × Oprof ). In Minicrypt, where one-way functions exist: (i) No one-way function f : Σ∗ → Σ∗ can be Oprof -saturated. (ii) Equivalently, every one-way function that exists in Minicrypt must depend on the ordering of its input symbols in an essential way. Proof. We use the general-alphabet form of Oprof (Remark 2.3): for a k-symbol alphabet Σ = {a0 , . . . , ak−1 }, Oprof (x) = (|x|a0 , . . . , |x|ak−1 ) ∈ Nk . Part (i): suppose f is Oprof -saturated and one-way. By [9, Theorem 2.1], f (x) depends only on Oprof (x) = (|x|a0 , . . . , |x|ak−1 ). An adversary with O⊤ who observes y = f (x) inverts f as follows. By the standard definition of one-way functions, the inverting algorithm receives (1n , y) where n = |x|, so n P is known. The adversary enumerates all profiles π ∈ Nk with i πi = n (at most (n + 1)k−1 many, polynomial in n for fixed k), and for each π evaluates f (ConstructFromProfile(π)) using Algorithm 1 and the publicly known f . Since f is Oprof -saturated, f takes the same value on every string sharing a profile; hence there exists some π ∗ among those enumerated with f (ConstructFromProfile(π ∗ )) = y. Setting x′ = ConstructFromProfile(π ∗ ) gives a string satisfying f (x′ ) = y. The entire procedure runs in time polynomial in n, contradicting the one-wayness of f . Part (ii): the contrapositive of part (i). If f is one-way in Minicrypt, then f is not Oprof -saturated, which means f (x) ̸= f (x′ ) for some x, x′ with Oprof (x) = Oprof (x′ ). Hence f distinguishes permutations of the same input. Remark 4.8. Proposition 4.7 gives a structural lower bound on one-way functions: they must be ordering-sensitive. Any candidate one-way function that is invariant under permutation of its input, for example, any function of the Hamming weight alone, cannot be one-way, even in Minicrypt. This is a consequence of observational structure, not of any hardness assumption. Toy example for cell (c). Let f (x) = |x|1 (Hamming weight, interpreted as an integer). This function depends only on the symbol count |x|1 , which is the second component of Oprof (x) = (|x|0 , |x|1 ); hence f is Oprof -saturated. By Proposition 4.7(i), f cannot be one-way in Minicrypt. Indeed, to invert f on a value v for an input of length n = |x|, Algorithm 1 constructs 0n−v 1v in O(n) time, giving a preimage with |x′ |1 = v. Proposition 4.9 (Cell (d): Cryptomania × O⊥ ). In Cryptomania, an adversary with observer O⊥ on the plaintext space cannot recover any information about the plaintext from the ciphertext, for any encryption scheme. Proof. Since O⊥ (m) = ⋆ for all m (Definition 2.2(i)), a machine receiving only O⊥ (m) receives the same input ⋆ regardless of m. No machine, regardless of computational power, can distinguish any two plaintexts from ⋆ alone: the adversary’s observation space contains no information about the plaintext. This is structural blindness: by [9, Proposition 8.2(ii)], PO⊥ = NPO⊥ = {∅, Σ∗ }. The existence of cryptographic primitives in Cryptomania is irrelevant, since the adversary cannot even pose the question of which plaintext was encrypted.
9
Toy example for cell (d): MR-OTP perfect secrecy. Let B = (2, 3) and consider the MR-OTP [8] with message M = (m1 , m2 ) ∈ Z2 × Z3 and key K = (k1 , k2 ) uniform on Z2 × Z3 . Ciphertext: C = ((m1 + k1 ) mod 2, (m2 + k2 ) mod 3). For any fixed c = (c1 , c2 ) and any m, the unique key mapping m to c is K = (c1 − m1 mod 2, c2 − m2 mod 3). Since K is uniform, Pr[C = c | M = m] = 1/6 for all m and c. Hence Pr[M = m | C = c] = Pr[M = m]: perfect secrecy [8, Theorem 1]. The adversary’s observer on the plaintext is O⊥ : the ciphertext carries zero information about m. Remark 4.10 (Cell (d) and the MR-OTP). Cell (d) describes the situation of an adversary facing the Mixed-Radix One-Time Pad [8] in the ciphertext-only setting (see Definition 5.1 in Section 5 for the formal definition of the Observer World and the adversary/defender asymmetry). By [8, Theorem 1], the MR-OTP achieves Shannon perfect secrecy [26]: the ciphertext distribution is identical for every plaintext, placing the adversary in the O⊥ -on-plaintext situation of Proposition 4.9. This holds in every world Wi , including Cryptomania: the perfect secrecy of the MR-OTP is not a consequence of the hardness assumptions of Cryptomania but of the information-theoretic structure of the cipher. Even the strongest cryptographic adversary in Cryptomania is reduced to O⊥ on the plaintext.
5
The Observer World: a sixth landscape
Definition 5.1 (Observer World). An Observer World is a pair WO = (Wi , O) where Wi is one of the five worlds of Definition 3.1 and O : Σ∗ → S is an observer in the hierarchy of [9]. In WO : • The computational assumptions of Wi hold for all parties. • The adversary’s input is O(x), not x: the adversary operates under observer O rather than O⊤ . • The defender’s input is O⊤ (x) = x: the defender has full access to the input. Remark 5.2 (Cryptographic interpretation of the asymmetry). The asymmetry between adversary (O) and defender (O⊤ ) in Definition 5.1 is deliberate and models the cryptographic setting: the defender generates and knows the key, while the adversary observes only the ciphertext (or a more informative projection of the input, depending on the attack model). The case O = O⊤ recovers the classical five-world framework with no observational constraint on the adversary. The following lemma constructs, for any O ≺ O⊤ , a language that is O-saturated but whose membership is independent of every five-world computational assumption. Lemma 5.3 (Observationally invariant, computationally independent language). Let O ≺ O⊤ . There exists a language L that is O-saturated and such that membership in L cannot be decided from any purely computational assumption about Wi alone. The language L constructed below may or may not belong to P or NP; the lemma asserts only that its membership is independent of the five-world assumptions. Proof sketch. Partition Σ∗ into ∼O -equivalence classes [u0 ]O , [u1 ]O , . . . , and let M0 , M1 , . . . enumerate all polynomial-time machines receiving O(x). For each e, pick a canonical representative u∗e ∈ [ue ]O and define [ue ]O ⊆ L iff Me rejects O(u∗e ) (a diagonalisation). The resulting L is a union of ∼O -classes, hence O-saturated; by construction, no Me decides L 10
correctly, so L ∈ / PO . The construction uses only the ∼O relation (a property of O alone) and makes no assumption about P vs NP, one-way functions, or public-key cryptography; hence membership in L is independent of all five-world computational assumptions. The full constructive proof is in Appendix A. Proposition 5.4 (The Observer World is not reducible to the five worlds). For O ≺ O⊤ , the Observer World WO = (Wi , O) is not equivalent to any of the five worlds Wj with observer O⊤ : no computational assumption about Wj implies the structural collapse PO = NPO ⊊ P, and no observational constraint in WO implies any of the computational assumptions of Wi . Proof. We exhibit the argument for O = Oprof ; the general case O ≺ O⊤ follows by the same structure using Lemma 5.3 for arbitrary O. No computational assumption implies the observational collapse. The structural collapse POprof = NPOprof ⊊ P is unconditional [9, Propositions 8.3–8.4]: it holds regardless of which Wi contains us, and hence cannot be a consequence of any computational assumption. By Lemma 5.3, there exists a language L that is Oprof -saturated and independent of all five-world assumptions; this witnesses the orthogonality of the two axes. No observational constraint implies any computational assumption. The observational constraint O ≺ O⊤ is a statement about the information available to the adversary, not about the computational difficulty of any problem. By [9, Theorem 8.5], computational hardness and observational saturation are independent: there exist languages in P that are not Oprof -saturated, and languages outside RE that are Oprof -saturated. The observational parameter O carries no information about the computational structure of Wi . Remark 5.5 (The Observer World as a sixth world). Proposition 5.4 shows that the parameter O adds genuinely new content to the five-world framework: it cannot be encoded as a computational assumption within the existing five worlds. The Observer World WO is therefore a sixth landscape, not a variation on an existing world, but an orthogonal dimension of the complexity landscape. The analogy with Impagliazzo’s construction is structural. Impagliazzo introduced five worlds by varying a single parameter (the existence of one-way functions) along a single axis. We introduce the Observer World by varying a second parameter (the observer O) along a second axis. The resulting landscape is two-dimensional: the five-world axis (computational) and the observational axis.
6
Observer worlds with broken invariants
The Syntactic Invariance Principle (SIP) of [10] states that a syntactic system cannot derive clauses that violate a syntactic invariant. In the observational setting, the observer O defines an observational invariant: a language L is O-invariant (equivalently, O-saturated; see Section 2) if membership in L is determined entirely by O(x). An Observer World with observer O places the adversary within the observational invariant defined by O: the adversary cannot access information that O discards. An Observer World with broken invariant is one in which the adversary finds a mechanism to circumvent this constraint, the observational analogue of SIP violation.
11
6.1
Three cases of invariant violation
Definition 6.1 (Oracle violation). In an Observer World WO = (Wi , O) with oracle violation, the adversary has observer O on the input but additionally has adaptive oracle access to queries q1 , q2 , . . . , qd on x, where each qj+1 may depend on the responses (x[q1 ], . . . , x[qj ]). The adversary’s total observation is the pair (O(x), (x[q1 ], . . . , x[qd ])). Remark 6.2 (Oracle violation and adaptive observers). As formalised in Remark 7.2 below (Section 7), an oracle queried adaptively is an adaptive observer of finite depth. Definition 6.1 is therefore the special case of an adaptive observer of depth d applied to an Observer World. The oracle-relative separations of the relativisation barrier [2] are separations in the hierarchy of adaptive Observer Worlds, not in the static observational hierarchy of [9]. Proposition 6.3 (Oracle violation and the MR-OTP). In the ciphertext-only setting of WO = (Wi , O⊥ ), oracle access to the ciphertext C = Enc(M, K) (where Enc denotes MR-OTP encryption: Ci = (Mi + Ki ) mod bi ) provides no information about the plaintext M for the MR-OTP [8], regardless of the number of oracle queries and regardless of which world Wi we are in. Proof. By [8, Theorem 1], the MR-OTP achieves perfect secrecy: for every plaintext M and every ciphertext c ∈ DB , Pr[C = c | M ] = |DB |−1 . In particular, C and M are independent random variables. We prove by induction on depth d that the adaptive query transcript (C[q1 ], . . . , C[qd ]) is independent of M . Base case (d = 0). The empty transcript carries no information; independence holds trivially. Inductive step. Assume (C[q1 ], . . . , C[qd−1 ]) is independent of M . Query qd is determined by the previous responses (C[q1 ], . . . , C[qd−1 ]); since these are independent of M , so is qd . The response C[qd ] is the qd -th coordinate of C, which by perfect secrecy is uniform on its range and independent of M (conditioning on any realisation of qd and the previous transcript does not change the distribution of C[qd ] given M , because C is independent of M unconditionally). Hence (C[q1 ], . . . , C[qd ]) is independent of M . By induction, the full transcript at any depth is independent of M , so oracle access to C provides no advantage to the adversary. Definition 6.4 (Side-channel violation). In an Observer World WO = (Wi , O) with sidechannel violation, the adversary has observer O on the input but additionally observes a second signal O′ (Comp) where Comp is the computation process of the defender (timing, power consumption, cache access patterns, etc.) and O′ : Process → S ′ is a second observer on that process. Remark 6.5 (Notation: oracle violation vs adaptive observer). Definition 6.1 writes query responses as x[qj ] (direct symbol access to the input string x). Definition 7.1 in Section 7 writes responses as ri = O(qi ) for an oracle O. The two are consistent: x[qj ] is the special case in which the oracle returns the qj -th symbol of the input, while O(qi ) allows more general queries whose address qi is generated adaptively from previous responses. Both are adaptive observers of finite depth in the sense of Definition 7.1. Remark 6.6. Side-channel violation is formally distinct from oracle violation: the additional observation is on the computation process, not on the input x. The combination 12
(O(x), O′ (Comp)) may exceed the limitations of O(x) alone if the computation process leaks information about the parts of x that O discards. This is the observational formalisation of side-channel attacks in cryptography. Definition 6.7 (Structural violation). In an Observer World WO = (Wi , O) with structural violation, the problem L is O-saturated (the adversary can pose the problem correctly under O) but the algorithm solving L produces output from which the adversary can recover information about the parts of x discarded by O. The computation betrays the observer’s invariant even though the problem statement does not. Remark 6.8 (Structural violation and the SIP). Definition 6.7 is the precise observational analogue of the Syntactic Invariance Principle of [10]. In the SIP, a syntactic calculus cannot derive clauses violating a syntactic invariant, but a semantic computation might produce such clauses as a side effect of solving a syntactically invariant problem. In Definition 6.7 the problem is O-invariant (syntactic level), but the algorithm’s output violates the invariant (semantic level).
6.2
The parametric family WOε
Definition 6.9 (Information distance between observers). Fix a prior PX on Σ∗ . For observers O1 ⪯ O2 , the information distance from O1 to O2 under PX is dinfo (O1 , O2 ) = IPX (X; O2 (X)) − IPX (X; O1 (X)), where IPX (X; Y ) denotes mutual information under PX . Note dinfo (O1 , O2 ) ≥ 0 since O1 ⪯ O2 implies I(X; O1 (X)) ≤ I(X; O2 (X)) by the data processing inequality [13]. Definition 6.10 (Parametric Observer World). Fix a prior PX on Σ∗ and an Observer World WO = (Wi , O) with O ≺ O⊤ strictly (so that dinfo (O, O⊤ ) > 0). For ε ∈ [0, 1], the parametric Observer World WOε = (WO , ε) is an Observer World in which the adversary’s effective observer is some Oε with O ⪯ Oε ⪯ O⊤ satisfying ε=
IP (X; Oε (X)) − IPX (X; O(X)) dinfo (O, Oε ) = X . dinfo (O, O⊤ ) IPX (X; O⊤ (X)) − IPX (X; O(X))
The denominator is positive by the strict inequality O ≺ O⊤ and the data processing inequality. • ε = 0: pure Observer World WO ; the adversary has O. • ε = 1: classical world; the adversary has O⊤ . • 0 < ε < 1: partial violation; the adversary has recovered some but not all of the discarded information. Remark 6.11. The information distance dinfo in Definition 6.10 requires a probability measure on Σ∗ and an entropy functional compatible with the observer. The precise formulation is an open direction; Appendix C discusses two concrete alternatives (statistical distance and channel capacity). The qualitative structure of WOε , interpolating between the pure Observer World (ε = 0) and the classical world (ε = 1), is well-defined without specifying the metric, since the endpoints are determined by the observers alone. 13
Remark 6.12 (Robustness with respect to the prior). The quantitative value of ε for a given Oε depends on the choice of prior PX . We conjecture that the qualitative results of Proposition 6.13, in particular, the identification of (Pessiland, Oprof , ε > 0) as the most informationally rich cell, are robust across the family of product priors and max-entropy priors. Appendix C provides examples supporting this conjecture. A formal robustness theorem is an open direction.
6.3
The most informationally rich cell
Proposition 6.13 (Pessiland × Oprof × ε > 0). The cell (Pessiland, Oprof , ε) for ε > 0 is the most informationally rich cell of the parametric table, in the sense that it simultaneously lacks all three sources of potential security. In this world: (i) NP problems are hard on average and no one-way function exists (Pessiland). (ii) The adversary in its pure state (ε = 0) cannot see the ordering of symbols (Oprof ). (iii) The adversary has partially broken the observational invariant (ε > 0), recovering ordering information through oracle queries, side channels, or structural violations. (iv) There is no computational security (no one-way functions in Pessiland), no invariant security (ε > 0 means the observational invariant of Oprof is partially broken), and no observational security in the pure sense (the adversary is no longer confined to Oprof ). This world is genuinely insecure for reasons that no single framework, five-world, SIP, or observational, addresses individually. Proof. Parts (i) and (ii): by definitions of Pessiland [16] and Oprof [9]. Part (iii): by Definition 6.10 with ε > 0. Part (iv): in Pessiland there are no one-way functions, so no computational security primitive exists. With ε > 0, the adversary’s effective observer Oε carries strictly more information about x than Oprof does (under PX , by Definition 6.10), so the observational invariant of Oprof is partially broken. The three sources of potential security, computational hardness, observational blindness, and invariant confinement, have all failed simultaneously. Remark 6.14 (Connection to the Base Recovery Problem). The Base Recovery Problem (BRP) of [7] asks an adversary to recover the base sequence B of an MR-OTP from plaintext-ciphertext pairs. In the world (Pessiland, Oprof , ε = 0), the BRP is not even well-posed for the adversary: the base sequence B encodes the structure of the cipher at the ordering level, which Oprof discards. With ε > 0, for instance, when the adversary has a side-channel on the encryption process, the BRP becomes increasingly tractable as ε increases. Whether the lower bound of [7, Theorem 8.10] on the query complexity of the BRP degrades gracefully with ε is Open Problem 6.15 below. Open Problem 6.15 (BRP complexity as a function of ε). Does the lower bound of [7, Theorem 8.10] on the query complexity of the Base Recovery Problem degrade gracefully as ε increases in the parametric Observer World (Pessiland, Oprof , ε)? Characterise the Q function f (ε) such that the BRP requires at least Ω( i bi · f (ε)) queries, with f (0) = 1 (the unconditional lower bound) and f (1) = 0 (classical world, where the BRP is informationtheoretically solvable with sufficient plaintext-ciphertext pairs). 14
7
Physical instantiation of the Observer World
The results of the preceding sections are mathematical. This section identifies connections between the observer-world framework and physical theory; each connection is formalised as an open problem. The author is a computer scientist, not a physicist. The observations below are offered as open questions, stated with precise mathematical hypotheses, not as established results. The three subsections follow a common pattern: a mathematical property of the observational hierarchy corresponds to a physical phenomenon, a cost, a transition, or a bound. In each case the mathematical structure was identified first and the physical correspondence found second. Each subsection closes with a precise formulation of the open problem. Numerical estimates are in Appendix C.
7.1
Adaptive observers, oracles, and the cost of observation
The observational hierarchy of [9] consists of non-adaptive observers: each O : Σ∗ → S is a fixed preprocessing map, independent of any computation that follows. A natural extension replaces O with an adaptive observer T : a decision tree in which each internal node is a query and each branch is a possible response. An adaptive observer of depth d makes at most d sequential queries, each potentially depending on previous responses. Definition 7.1 (Adaptive observer and parametrised complexity classes). An adaptive observer of depth d is a protocol that sequentially issues queries q1 , q2 , . . . , qd to the input string x and collects responses ri = x[qi ] (or more generally ri = O(qi ) for an oracle O), where each query qi+1 may depend on the previous responses r1 , . . . , ri . The transcript Td (x) = (r1 , . . . , rd ) is the adaptive observer’s output. The observer-and-depth parametrised class is n o PO,d = L ∃ poly-time TM M : M (O(x), Td (x)) decides L . Non-adaptive observers of [9] correspond to d = 0. Remark 7.2 (Oracles are adaptive observers). A computational oracle O : Σ∗ → {0, 1}, queried adaptively with query sequence q1 , q2 , . . . , qd where each qi+1 may depend on the previous responses (O(q1 ), . . . , O(qi )), is an adaptive observer of depth d: its transcript is (O(q1 ), . . . , O(qd )). The non-adaptive observers of [9] correspond to the special case d = 0 (all queries are fixed in advance, independent of responses). Oracle-relative separations in complexity theory, in particular, the relativisation barrier of Baker, Gill, and Solovay [2], are therefore separations in the hierarchy of adaptive Observer Worlds, not in the non-adaptive hierarchy studied in [9]. The adaptive hierarchy has a physical cost. By Landauer’s principle [18], each query that is recorded and subsequently erased to allow cyclic operation dissipates at least kB T ln 2 joules. A system operating as an adaptive observer of depth d in a cycle must erase at least d bits per cycle, at a minimum thermodynamic cost of d · kB T ln 2 joules per cycle. Remark 7.3 (The Maxwell demon as adaptive observer). The Maxwell demon of [5] is an adaptive observer of depth proportional to the number of molecules it measures: each measurement is a query on the velocity of a molecule, and the demon’s decision to open or close the partition is the query-dependent response. Bennett’s resolution of the paradox [5], that the demon must erase its measurement records at a cost that cancels the apparent entropy decrease, is the statement that an adaptive observer cannot operate cyclically 15
without paying the Landauer cost of its depth. The impossibility of a perpetual motion machine is the theorem that no physical system can operate as a non-trivial adaptive observer in a cycle without this cost. Open Problem 7.4 (Adaptive observer hierarchy and Landauer cost). Formalise the hierarchy of adaptive observers as an extension of the non-adaptive hierarchy of [9], characterise the complexity classes PO,d and NPO,d parametrised by observer O and adaptive depth d, and determine whether the Landauer cost of depth provides a physical lower bound on the complexity of transitioning between levels of the hierarchy. The information distance dinfo of Definition 6.9 would provide a natural measure for such a lower bound.
7.2
Quantum measurement as an observational transition
Prior to measurement, a quantum system in superposition is one in which the observer has O⊥ on the definite value of the observable: the value is not determined in the observation space of any non-trivial observer. After measurement, the observer has a definite value: a transition to a higher level of the observational hierarchy. The collapse of the wave function, in this reading, is the transition from a lower to a higher level of the observational hierarchy, and the irreversibility of that transition is the Landauer cost of recording the measurement outcome. The decoherence programme [33] provides a continuous version of this picture: the quantum-to-classical transition is the gradual suppression of interference terms as the system becomes entangled with its environment, corresponding to the continuous transition from an observer that can detect interference (closer to O⊤ in the quantum extension of the hierarchy) to one that cannot (closer to Oprof in the classical limit). The formal extension of the observational hierarchy to quantum systems would replace O : Σ∗ → S with O : H → M, where H is a Hilbert space and M is a measurement space; the appropriate formalism is that of positive operator-valued measures (POVMs) [21]. Open Problem 7.5 (Quantum extension of the observational hierarchy). Construct a quantum extension of the observational hierarchy in which the non-adaptive observers of [9] are the classical limit, decoherence corresponds to a downward transition in the hierarchy, and the Landauer cost of measurement is the energy required to move between levels. Determine whether the five-world framework extends naturally to this quantum setting.
7.3
The cosmological bit budget and the physical ceiling of the observational hierarchy
The holographic bound of Bekenstein [3, 4] and ’t Hooft–Susskind [30, 29] limits the information content of any physical region to at most A/4ℓ2P bits, where A is the area of the bounding surface and ℓP is the Planck length. For the observable universe, this gives approximately 10122 bits, a finite number. The Margolus-Levitin bound [20] limits the total number of elementary operations a physical system of energy E can perform per unit time to 2E/h; integrated over the lifetime of the observable universe, this gives approximately 10121 total operations. These bounds imply that the complete observer O⊤ of the abstract hierarchy is not phys physically realisable: the physical O⊤ has capacity at most 10122 bits, and lies strictly 16
below the mathematical O⊤ in the observational order. The observational hierarchy, when instantiated in a physical universe with finite information capacity, has a finite, measurable ceiling. The 203-bit temporal bound and its origin The starting point for the following observation was a computer-science argument: to index all physically distinguishable moments in the lifetime of the observable universe, one needs a pigeonhole with one slot per Planck-time step, and the number of bits required to address that pigeonhole is ⌈log2 Nt ⌉, where Nt is the number of Planck-time steps since the Big Bang. The numerical value of Nt was computed with the assistance of an AI language model using standard physical values: the age of the universe (≈ 4.3 × 1017 s) and the Planck time (tP ≈ 5.39 × 10−44 s), giving Nt ≈ 8 × 1060 and ⌈log2 Nt ⌉ ≈ 203 bits. The author verified the order of magnitude and subsequently found that this specific calculation already appears in the literature [23], though not in the context of observational hierarchies. The idea of applying the pigeonhole argument to cosmic time in order to characterise the informational cost of the temporal coordinate of Oprof originated with the author. Having established that 203 bits suffice to index cosmic time, the author then asked whether this figure coincides with the maximum entropy generation rate of a physical true random number generator, that is, whether the informational compression of cosmic time has a direct structural counterpart in the universe’s capacity to generate randomness. The answer is negative, the Margolus-Levitin bound gives approximately 10121 total operations over the lifetime of the observable universe, requiring approximately 402 bits to index. The original hypothesis does not hold. However, the investigation yields a more precise structural observation than the one originally sought. The gap between 203 and 402 reflects the factor of 2 in the MargolusLevitin bound 2E/h, which is structural. The comparison reveals: • 203 bits suffice to index all of cosmic time at Planck resolution. • ≈ 402 bits suffice to index the total number of operations the universe can have performed. • ≈ 10122 bits describe the total state space by the Bekenstein bound. The observer Oprof , which discards the temporal coordinate, discards the informationally cheapest dimension of the physical universe, the one that costs only 203 bits, but loses all causal structure in doing so. This asymmetry between the informational cost of time (minimal) and its structural role (maximal, as the carrier of all causal order) is the physical counterpart of the central result of [9]: that Oprof -saturation is a structurally strong condition that eliminates all ordering-dependent difficulty. Remark 7.6 (Connection to the five worlds). In each of the five worlds of Impagliazzo [16], the bounds of Sections 7.1–7.3 apply: they are consequences of the physics of the universe, not of the computational assumptions that define the worlds. An Observer World WO instantiated in the physical universe therefore carries the constraint that the adaptive depth of any physically realisable observer is bounded by 10121 total operations (assuming each query costs at least one elementary operation), and the total information budget is 10122 bits. The temporal coordinate costs 203 bits of that budget; this is a negligible 17
fraction (203/10122 ≈ 0) of the total, yet it is the dimension that carries all causal order. The remaining ≈ 10122 bits describe spatial and energetic state. Whether this split has consequences for the complexity of problems in the cells of the world-observer table (Section 4) is an open question. Open Problem 7.7 (Cosmological cutoff and the observational hierarchy). Does the observational hierarchy, when instantiated in a physical universe with the Bekenstein and Margolus-Levitin bounds as constraints, predict a natural cutoff adaptive depth that coincides with the physical bounds? Is there a sense in which the 203-bit temporal bound emerges from the theory rather than being imported from physics as an external parameter?
A remark on the scope of these connections The connections identified in Sections 7.1–7.3 share a common structure: a mathematical property of the observational hierarchy (non-adaptivity, the gap between levels, the finite phys ceiling of O⊤ ) corresponds to a physical phenomenon (thermodynamic cost of measurement, wave function collapse, the holographic bound). In each case the mathematical structure was identified first and the physical correspondence found second. Whether these correspondences reflect a deeper unity, whether the laws of thermodynamics are, in some precise sense, theorems about the observational hierarchy of physical systems, is a question that the present framework cannot answer, but for which it offers a precise mathematical vocabulary. The formalisation would require, at minimum, a probability measure on physical histories, a dynamics compatible with the observational order, and an entropy functional consistent with both Landauer’s principle and the holographic bound. These things are not assembled here; identifying them as a coherent research programme is the contribution of this section.1
8
Conclusion
The five worlds of Impagliazzo describe a line: a single axis parametrising the existence of computational hardness and cryptographic primitives. This paper has shown that the observational hierarchy of [9] defines a second, orthogonal axis, producing a twodimensional landscape in which the five worlds are five columns and the observational levels are the rows. The central result, that the structural collapse POprof = NPOprof ⊊ P holds unconditionally in all five worlds, shows that the two axes are genuinely independent: no computational assumption implies the observational collapse, and no observational constraint implies any computational assumption. The Observer World WO formalises this independence as a sixth landscape. The labeled cells (a)–(d) of the world-observer table identify four phenomena that the fiveworld framework cannot express: the observational collapse in Algorithmica despite P = NP, the non-additive interaction of hardness and blindness in Pessiland, the ordering-sensitivity lower bound on one-way functions in Minicrypt, and the O⊥ -blindness security of the MR-OTP in the Cryptomania × O⊥ cell. 1
The numerical estimates in Section 7.3 were computed with AI assistance and verified by the author. All scientific ideas and conclusions are the author’s own.
18
The parametric family WOε extends the framework to worlds in which the observational invariant is partially violated, with the most informationally rich cell being Pessiland × Oprof × ε > 0: a world in which computational, invariant, and observational security have all failed simultaneously. Section 7 identifies three connections between the Observer World framework and physical information limits, thermodynamics (Landauer cost of adaptive observation), quantum mechanics (decoherence as a downward transition in the hierarchy), and cosmology (the holographic bound as a physical ceiling on O⊤ ), and states a precise open problem for each. The Observer World provides a unified language for modelling adversaries in cryptography, extending Impagliazzo’s five worlds with an orthogonal axis that captures what the adversary can observe. Formal open directions include: characterising how the BRP query lower bound degrades with ε (Open Problem 6.15); formalising the hierarchy of adaptive observer complexity classes PO,d and the Landauer cost of depth as a physical lower bound (Open Problem 7.4); constructing a quantum extension of the observational hierarchy (Open Problem 7.5); and determining whether the cosmological bounds predict a natural cutoff depth (Open Problem 7.7). The information metric for ε and the robustness of qualitative results with respect to the prior are addressed in Appendix C and remain an open direction. Personal note. Several of the connections developed in this paper emerged unexpectedly during work on the Observer paper [9]. The observation that the five worlds presuppose O⊤ silently led naturally to the question of what happens when the adversary’s observer is constrained. The connection to thermodynamics emerged from the question of what it costs an observer to become more powerful. The 203-bit cosmological bound emerged from applying a pigeonhole argument to the indexing of Planck-time steps, an idea that originated with the author and was verified numerically with AI assistance. The connection to the SIP emerged from asking what it means for an adversary to circumvent an observational constraint. Each connection was forced by the logic of the previous one; none was planned in advance.2
A
Proof of Lemma 5.3
This appendix provides the complete constructive proof of Lemma 5.3. Full proof of Lemma 5.3. Let O ≺ O⊤ ; since O ̸≃ O⊤ , there exist x0 = ̸ x1 with O(x0 ) = O(x1 ). Enumerate the ∼O -equivalence classes as [u0 ]O , [u1 ]O , [u2 ]O , . . . (where [u]O = {x | O(x) = O(u)}) and let M0 , M1 , M2 , . . . be a standard enumeration of all deterministic polynomial-time Turing machines that receive O(x) as input. For each e ∈ N, choose a canonical representative u∗e ∈ [ue ]O and define: [ue ]O ⊆ L
Me rejects O(u∗e ).
⇐⇒
L is O-saturated. By construction, L is a union of complete ∼O -classes. If O(x) = O(y) then x and y are in the same class, so either both are in L or neither is: x ∈ L ⇐⇒ y ∈ L. By Definition 3.2 of [9], L is O-saturated. 2
The author used an artificial intelligence based language assistant to support text traslation, revision and numerical verification. All scientific ideas and conclusions are the author’s own.
19
L∈ / PO . Suppose for contradiction that some Me decides L under observer O. Consider the class [ue ]O : • If Me accepts O(u∗e ): then by our construction, [ue ]O ̸⊆ L, so u∗e ∈ / L. But Me accepts ∗ ∗ O(ue ), so Me decides ue ∈ L: contradiction. • If Me rejects O(u∗e ): then [ue ]O ⊆ L, so u∗e ∈ L. But Me rejects O(u∗e ): contradiction. In both cases Me is wrong on u∗e , so Me does not decide L. Since e was arbitrary, L ∈ / PO . Independence from five-world assumptions. The construction uses only: the ∼O relation (a property of the observer), the canonical enumeration of polynomial-time TMs (a standard recursion-theoretic object), and the choice of representatives. No assumption about P vs NP, about the existence of one-way functions, or about public-key cryptography is invoked at any step. Hence membership in L is independent of all five-world assumptions.
B
Profile preimage: correctness and complexity
This appendix provides the complete proof of Lemma 4.6. Full proof of Lemma 4.6. Correctness. Algorithm 1 appends ci copies of symbol ai for each i ∈ {0, . . . , k − 1}. By construction, the resulting string x′ satisfies |x′ |ai = ci for all i: symbol ai appears exactly ci times and no other appearances are introduced. Hence Oprof (x′ ) = (c0 , . . . , ck−1 ) = π. Complexity. The outer loop executes k iterations. In iteration i, the append operation is performed ci times; each append is O(1) amortised over a dynamic array. Total operations: Pk−1 i=0 ci = n. Time complexity: O(n). ck−1 Remark on uniqueness. Algorithm 1 returns the canonically sorted string ac00 ac11 · · · ak−1 . For the purposes of Proposition 4.7, any string with profile π suffices; the sorted string is one concrete choice.
C
Cosmological calculations and alternative metrics
This appendix documents the numerical calculations cited in Section 7.3, and the alternative information metrics discussed in Remarks 6.11 and 6.12.
C.1
Cosmological bit budget
Let tuniverse ≈ 4.3 × 1017 s be the age of the observable universe and tP ≈ 5.39 × 10−44 s be the Planck time (standard CODATA values). The number of Planck-time steps since the Big Bang is: tuniverse 4.3 × 1017 Nt = ≈ ≈ 7.98 × 1060 . −44 tP 5.39 × 10 The number of bits to index all such steps is: ⌈log2 Nt ⌉ = ⌈log2 (7.98 × 1060 )⌉ = ⌈202.6⌉ = 203. These are order-of-magnitude estimates; the physical constants carry observational uncertainties at the few-percent level, which do not affect the rounded result. This calculation 20
was verified numerically with AI assistance and is also reported in [23] (in a different context). For the Margolus-Levitin bound [20]: total observable-universe energy E ≈ 1069 J, giving ≈ 2E/h · tuniverse ≈ 10121 operations and ⌈log2 10121 ⌉ ≈ 402 bits.
C.2
Alternative metrics for ε
Statistical distance. dTV info (O1 , O2 ) = Ex∼PX [dTV (δO1 (x) , δO2 (x) )] where dTV is total variation. For deterministic observers, this reduces to the probability under PX that O1 (x) ̸= O2 (x), which is 0 when O1 = O2 and positive otherwise. This gives the same ε = 0 and ε = 1 endpoints as Definition 6.10. Channel capacity. dcap info (O1 , O2 ) = cap(O2 )−cap(O1 ) where cap(O) = maxPX I(X; O(X)) is the channel capacity of observer O. This is prior-independent but requires solving a maximisation problem over all priors. Both alternatives give the same qualitative picture for the example of Section 6.3: the cell (Pessiland, Oprof , ε > 0) remains the most informationally rich regardless of which metric is used, because all three metrics (mutual information from Definition 6.9, statistical distance, and channel capacity) agree on ε = 0 (pure Observer World) and ε = 1 (classical world).
C.3
Landauer cost and reversible computation
Landauer’s principle [18] states that erasing one bit at temperature T requires at least kB T ln 2 joules. For an adaptive observer of depth d operating cyclically with b bits per response, the minimum cost per cycle is bd · kB T ln 2 joules. The hypothesis that the observer operates cyclically (and thus must erase) is a physical modelling assumption, not derived from the mathematical framework [5]. Reversible computation can in principle approach the Landauer bound arbitrarily closely; the bound is a lower limit, not a prediction of typical behaviour.
References [1] Scott Aaronson and Avi Wigderson. Algebrization: A new barrier in complexity theory. ACM Transactions on Computation Theory, 1(1):2:1–2:54, 2009. [2] Theodore Baker, John Gill, and Robert Solovay. Relativizations of the P = NP question. SIAM Journal on Computing, 4(4):431–442, 1975. [3] Jacob D. Bekenstein. Black holes and entropy. Physical Review D, 7(8):2333–2346, 1973. [4] Jacob D. Bekenstein. Universal upper bound on the entropy-to-energy ratio for bounded systems. Physical Review D, 23(2):287–298, 1981. [5] Charles H. Bennett. The thermodynamics of computation — a review. International Journal of Theoretical Physics, 21(12):905–940, 1982. [6] David Blackwell. Equivalent comparisons of experiments. The Annals of Mathematical Statistics, 24(2):265–272, 1953. 21
[7] Fabio Francesco Gabriele Buono. From bits to mixed-radix keys: Horner decomposition, uniform sampling, and the information-theoretic QKD interface of the MR-OTP. 2026. arXiv preprint arXiv:2606.18526. [8] Fabio Francesco Gabriele Buono. New ideas on a new old type of cipher: The mixed-radix one-time pad. 2026. arXiv preprint arXiv:2606.16040. [9] Fabio Francesco Gabriele Buono. Observers, symmetries, and the hierarchy of language classes: A theory of computation parameterised by the observer, 2026. arXiv:submit/7752238 [cs.CR]. [10] Fabio Francesco Gabriele Buono. Syntactic systems cannot see semantic invariants. 2026. arXiv preprint arXiv:2606.17275. [11] Sean Carroll. From Eternity to Here: The Quest for the Ultimate Theory of Time. Dutton, New York, 2010. [12] Noam Chomsky. Three models for the description of language. IRE Transactions on Information Theory, 2(3):113–124, 1956. [13] Thomas M. Cover and Joy A. Thomas. Elements of Information Theory. Wiley, 2 edition, 2006. [14] David Deutsch. The Fabric of Reality. Penguin, London, 1997. [15] Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, San Francisco, CA, 1979. [16] Russell Impagliazzo. A personal view of average-case complexity. In Proceedings of the 10th Annual Structure in Complexity Theory Conference, pages 134–147. IEEE, 1995. [17] Jonathan Katz and Yehuda Lindell. Introduction to Modern Cryptography. CRC Press, 2 edition, 2014. [18] Rolf Landauer. Irreversibility and heat generation in the computing process. IBM Journal of Research and Development, 5(3):183–191, 1961. [19] Seth Lloyd. Ultimate physical limits to computation. Nature, 406:1047–1054, 2000. [20] Norman Margolus and Lev B. Levitin. The maximum speed of dynamical evolution. Physica D: Nonlinear Phenomena, 120(1–2):188–195, 1998. [21] Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2000. [22] Roger Penrose. The Road to Reality: A Complete Guide to the Laws of the Universe. Jonathan Cape, London, 2004. [23] David Pratten. Addressing the observable universe, 2008. urlhttps://davidpratten.com/2008/02/11/addressing-the-observable-universe/. [24] Alexander A. Razborov and Steven Rudich. Natural proofs. Journal of Computer and System Sciences, 55(1):24–35, 1997. 22
[25] Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. Journal of the ACM, 56(6):34:1–34:40, 2009. [26] Claude E. Shannon. Communication theory of secrecy systems. Bell System Technical Journal, 28(4):656–715, 1949. [27] Imre Simon. Piecewise testable events. In Automata Theory and Formal Languages, volume 33 of Lecture Notes in Computer Science, pages 214–222. Springer, 1975. [28] Michael Sipser. Introduction to the Theory of Computation. Cengage Learning, 3 edition, 2012. [29] Leonard Susskind. The world as a hologram. Journal of Mathematical Physics, 36(11):6377–6396, 1995. [30] Gerard ’t Hooft. Dimensional reduction in quantum gravity. In Salamfestschrift, pages 284–296. World Scientific, 1993. Also available as arXiv:gr-qc/9310026. [31] Vlatko Vedral. Decoding Reality: The Universe as Quantum Information. Oxford University Press, 2010. [32] John A. Wheeler. Information, physics, quantum: The search for links. In Complexity, Entropy and the Physics of Information, pages 3–28. Addison-Wesley, 1990. [33] Wojciech H. Zurek. Decoherence, einselection, and the quantum origins of the classical. Reviews of Modern Physics, 75(3):715–775, 2003. [34] Konrad Zuse. Rechnender Raum. Friedrich Vieweg & Sohn, Braunschweig, 1969. English translation: Calculating Space, MIT Technical Translation AZT-70-164GEMIT, 1970.
23