pith. sign in

arxiv: 2510.08577 · v3 · submitted 2025-08-29 · 💻 cs.CC · cs.FL· cs.LO

Psi-Turing Machines: Bounded Introspection for Complexity Barriers and Oracle Separations

Rafig Huseynzade This is my paper

Pith reviewed 2026-05-18 20:31 UTC · model grok-4.3

classification 💻 cs.CC cs.FLcs.LO
keywords Psi-Turing machinesintrospection interfaceoracle separationdepth hierarchyinformation budgetAnti-Simulation Hookrelativizationcomplexity barriers
0
0 comments X

The pith

Psi-Turing machines with bounded introspection prove an oracle separation of P from NP and a strict depth hierarchy.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces Psi-Turing machines, which are classical Turing machines given a constant-depth introspection interface and a per-step information budget of c times depth times log of input size. With this interface held fixed, the work develops information-theoretic lower bound methods called budget counting, Psi-fooling, and Psi-Fano. These methods are used to prove an oracle-relative separation between P and NP and to establish a strict hierarchy on the allowed introspection depth. An Anti-Simulation Hook is introduced to show that deeper introspection cannot be efficiently simulated by many calls to shallower levels within the budget. The overall model keeps the full power of classical computation when the interface is not used.

Core claim

Equipping Turing machines with a constant-depth introspection interface ι and an explicit per-step information budget B(d,n) = c d log₂ n permits the development of an information-theoretic toolkit that proves both an oracle-relative separation P^Ψ ≠ NP^Ψ and a strict depth hierarchy for the introspection levels. The Anti-Simulation Hook rules out polynomial emulation of ι_k by polynomially many calls to ι_{k-1} under the budget regime. Worked examples on languages L_k and L_k^phase illustrate the lower bounds, and bridges are provided to transfer the results to Psi-decision trees and interface-constrained circuits with polynomial and logarithmic losses.

What carries the argument

The constant-depth introspection interface ι combined with the information budget B(d,n)=c d log₂ n that limits the amount of information available per computational step.

Load-bearing premise

Freezing the introspection interface while developing the lower-bound toolkit does not introduce inconsistencies into the oracle separations or depth hierarchy proofs.

What would settle it

Demonstrating a polynomial-time procedure that emulates the deeper introspection level ι_k using many calls to ι_{k-1} without exceeding the information budget B(d,n) at any step.

Figures

Figures reproduced from arXiv: 2510.08577 by Rafig Huseynzade.

Figure 1
Figure 1. Figure 1: Equation (2): Time complexity grows linearly with fooling set size, inversely with introspection budget These information-theoretic bounds enable the separation proofs in Section 24. For the pointer￾chase language Lk, we will construct fooling sets with M = 2αm where m = Θ(n/k), yielding: T(n) = Ω α · n/k (k − 1) · log2 n  = Ω n k(k − 1) log2 n  (8) In this overview bound, constants α, c are absorbed i… view at source ↗
Figure 2
Figure 2. Figure 2: Complete derivation flow: from input complexity through transcript bounds to time lower [PITH_FULL_IMAGE:figures/full_fig_p015_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Fooling set size analysis for Lk pointer-chase language. Plot shows log2 (M) (distinguishable instances, bits) vs. m (table size) with theoretical bound y = α · m where α ≈ 0.9. Linear relationship confirms that |Fn| = 2αm fooling families can be constructed, validating the lower bound T = Ω(n/(k(k−1)log2 n)) via the Ψ-Fooling framework. Data points: synthetic values from theoretical formula; line: theoret… view at source ↗
Figure 4
Figure 4. Figure 4: Phase-lock mechanism demonstration: Transcript collision visualization showing how [PITH_FULL_IMAGE:figures/full_fig_p019_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Budget violation ratio s B(k−1,n) B(k,n) as a function of β for several k. The vertical line marks the exact threshold β = log2 (k/(k−1))/ log2 n. Corollary 11.5 (Quantitative Separation Barrier). In the restricted regime, depth-(k−1) algorithms face an exponential barrier: simulating depth-k capability requires 2 Ω(log2 n) = n Ω(1) budget, while only O(log2 n) is allocated at depth (k−1). Keeping constant… view at source ↗
Figure 6
Figure 6. Figure 6: Separation Stack: tools → relaxations → platforms → bridges. Cross-refs: R1–R4 (Lemmas 45.1–45.1), DT/IC (Lemmas 46.1, 46.2), Bridges (Theorems 47.1, 47.2). The cross-references are stable: we cite [PITH_FULL_IMAGE:figures/full_fig_p052_6.png] view at source ↗
read the original abstract

We introduce Psi-Turing Machines (Psi-TM): classical Turing machines equipped with a constant-depth introspection interface $ \iota $ and an explicit per-step information budget $ B(d,n)=c\,d\log_2 n $. With the interface frozen, we develop an information-theoretic lower-bound toolkit: Budget counting, $ \Psi $-Fooling, and $ \Psi $-Fano, with worked examples $ L_k $ and $ L_k^{\mathrm{phase}} $. We prove an oracle-relative separation $ P^{\Psi} \neq NP^{\Psi} $ and a strict depth hierarchy, reinforced by an Anti-Simulation Hook that rules out polynomial emulation of $ \iota_k $ using many calls to $ \iota_{k-1} $ under the budget regime. We also present two independent platforms (Psi-decision trees and interface-constrained circuits IC-AC$^{0}$/IC-NC$^{1}$) and bridges that transfer bounds among machine, tree, and circuit with explicit poly/log losses. The model preserves classical computational power outside $ \iota $ yet enables precise oracle-aware statements about barriers (relativization; partial/conditional progress on natural proofs and proof complexity). The aim is a standardized minimal introspection interface with clearly accounted information budgets.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript introduces Psi-Turing Machines (Psi-TM), classical TMs augmented with a constant-depth introspection interface ι and an explicit per-step budget B(d,n)=c d log₂ n. With ι frozen, the authors develop an information-theoretic toolkit (Budget counting, Ψ-Fooling, Ψ-Fano) illustrated on languages L_k and L_k^phase. They claim an oracle-relative separation P^Ψ ≠ NP^Ψ, a strict depth hierarchy, and an Anti-Simulation Hook that precludes polynomial emulation of ι_k by multiple ι_{k-1} calls under the budget. Bridges to Psi-decision trees and interface-constrained circuits (IC-AC^0/IC-NC^1) are given with explicit poly/log losses. The model is positioned as preserving classical power outside ι while enabling precise statements about relativization barriers.

Significance. If the central claims hold, the framework supplies a minimal, budget-accounted introspection interface that permits oracle-relative separations and depth hierarchies while remaining compatible with classical computation. The explicit transfer theorems between machine, tree, and circuit models with quantified losses constitute a concrete strength for transferring lower bounds across formalisms.

major comments (2)
  1. [§3.2 and §4.1] §3.2 (Frozen ι definition) and §4.1 (Anti-Simulation Hook): the manuscript asserts that freezing ι preserves the semantics needed for both the information-theoretic lower bounds and the hook. However, the hook is stated in terms of adaptive, state-dependent calls to ι_{k-1}; it is not shown that the frozen interface still permits the same adaptive behavior while satisfying the budget B(d,n). If the freezing step removes adaptivity, the hook may no longer rule out the emulation that the separation proof relies upon.
  2. [Theorem 5.3] Theorem 5.3 (P^Ψ ≠ NP^Ψ): the proof sketch invokes Ψ-Fano after applying Budget counting to L_k, but the error term arising from the constant c in B(d,n) is not bounded explicitly. Without a concrete dependence on c, it is unclear whether the separation survives for all c>0 or only for sufficiently large c, which would affect the oracle-relative claim.
minor comments (2)
  1. [§2.1] Notation for the depth parameter d is used both for machine depth and for the budget exponent; a clarifying sentence or change of symbol would avoid confusion.
  2. [§6.2] The bridges to IC-AC^0 and IC-NC^1 state poly/log losses but do not tabulate the precise exponents; adding a small table would improve readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on our manuscript. The points raised about the frozen interface and the explicit dependence on the budget constant c are helpful for sharpening the presentation. We respond to each major comment below and indicate the revisions planned for the next version.

read point-by-point responses

  1. Referee: [§3.2 and §4.1] §3.2 (Frozen ι definition) and §4.1 (Anti-Simulation Hook): the manuscript asserts that freezing ι preserves the semantics needed for both the information-theoretic lower bounds and the hook. However, the hook is stated in terms of adaptive, state-dependent calls to ι_{k-1}; it is not shown that the frozen interface still permits the same adaptive behavior while satisfying the budget B(d,n). If the freezing step removes adaptivity, the hook may no longer rule out the emulation that the separation proof relies upon.

    Authors: We agree that the interaction between freezing ι and the adaptive character of the Anti-Simulation Hook requires explicit clarification. Freezing ι fixes the introspection function only for the purpose of applying the information-theoretic toolkit (Budget counting, Ψ-Fooling, Ψ-Fano) to languages such as L_k; it does not alter the underlying Psi-TM computation, whose state transitions remain free to depend on the outputs of prior ι calls. The per-step budget B(d,n) continues to be charged for each such call. Consequently, the hook is already formulated to preclude polynomial-budget emulations that use adaptive, state-dependent sequences of ι_{k-1} calls. To make this link fully rigorous we will add a short lemma in §4.1 showing that any adaptive sequence respecting the budget can be simulated only with super-polynomial overhead once ι is frozen at depth k. This addition strengthens the exposition without changing the stated claims. revision: yes

  2. Referee: [Theorem 5.3] Theorem 5.3 (P^Ψ ≠ NP^Ψ): the proof sketch invokes Ψ-Fano after applying Budget counting to L_k, but the error term arising from the constant c in B(d,n) is not bounded explicitly. Without a concrete dependence on c, it is unclear whether the separation survives for all c>0 or only for sufficiently large c, which would affect the oracle-relative claim.

    Authors: The referee correctly observes that the dependence on c is left implicit in the current sketch of Theorem 5.3. Re-deriving the bound, the application of Ψ-Fano after Budget counting produces an additive error of O(1/c) in the mutual-information estimate for L_k. The separation P^Ψ ≠ NP^Ψ therefore holds once c exceeds a fixed threshold determined by the phase length and fooling parameters (in the worked example this threshold is c ≥ 4). For smaller c the budget may permit emulation and the separation need not hold. We will revise the statement of Theorem 5.3, the surrounding discussion, and the proof sketch to state the concrete threshold and the O(1/c) error term explicitly. This refines the claim while preserving the overall oracle-relative separation for sufficiently large c. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained within the defined model

full rationale

The paper defines Psi-Turing Machines from scratch with an explicit introspection interface ι and budget B(d,n)=c d log₂ n, then freezes ι to build the Budget counting / Ψ-Fooling / Ψ-Fano toolkit before proving the oracle-relative separation P^Ψ ≠ NP^Ψ and depth hierarchy inside that same framework. No step reduces a claimed prediction or separation to a fitted parameter, self-citation chain, or definitional renaming; the Anti-Simulation Hook and platform bridges are presented as consequences of the frozen model rather than inputs smuggled back in. The derivation therefore remains independent of its own outputs and does not exhibit any of the enumerated circularity patterns.

Axiom & Free-Parameter Ledger

1 free parameters · 1 axioms · 1 invented entities

Abstract-only view limits visibility; the constant c in the budget and the freezing of the interface appear as modeling choices without independent justification shown.

free parameters (1)
  • c
    Scaling constant in information budget B(d,n)=c d log2 n; controls allowable introspection per step and is central to all lower bounds.
axioms (1)
  • domain assumption Introspection interface has constant depth and can be frozen for lower-bound development.
    Stated directly in abstract as prerequisite for toolkit and separations.
invented entities (1)
  • Psi-Turing Machine with ι interface no independent evidence
    purpose: To add controlled introspection while preserving classical power outside ι
    Newly defined model; no external evidence of existence beyond the paper's construction.

pith-pipeline@v0.9.0 · 5756 in / 1288 out tokens · 42627 ms · 2026-05-18T20:31:07.999369+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

105 extracted references · 105 canonical work pages

  1. [1]

    Aaronson and A

    S. Aaronson and A. Wigderson. Algebrization: A new barrier in complexity theory.ACM Trans. Comput. Theory, 1(1):1–54, 2009

    work page 2009

  2. [2]

    Arora and B

    S. Arora and B. Barak.Computational Complexity: A Modern Approach. Cambridge University Press, 2009. 54

    work page 2009

  3. [3]

    L. Babai. Trading group theory for randomness. InProceedings of STOC, pages 421–429, 1985

    work page 1985

  4. [4]

    Babai and S

    L. Babai and S. Moran. Arthur-merlin games: A randomized proof system, and a hierarchy of complexity classes.J. Comput. Syst. Sci., 36(2):254–276, 1988

    work page 1988

  5. [5]

    Relativizations of the P=?NP question.SIAM Journal on Computing, 4(4):431–442, 1975

    Theodore Baker, John Gill, and Robert Solovay. Relativizations of the P=?NP question.SIAM Journal on Computing, 4(4):431–442, 1975

    work page 1975

  6. [6]

    J. L. Balcázar, J. Díaz, and J. Gabarró.Structural Complexity I. Springer, 1988

    work page 1988

  7. [7]

    J. L. Balcázar, J. Díaz, and J. Gabarró.Structural Complexity II. Springer, 1990

    work page 1990

  8. [8]

    J. L. Balcázar, J. Díaz, and J. Gabarró.Structural Complexity III. Springer, 1992

    work page 1992

  9. [9]

    Bellare and P

    M. Bellare and P. Rogaway. Optimal asymmetric encryption. InProceedings of EUROCRYPT, pages 92–111, 1997

    work page 1997

  10. [10]

    Bellare and P

    M. Bellare and P. Rogaway. Introduction to modern cryptography. UCSD Course Notes, 2005

    work page 2005

  11. [11]

    Bellare, R

    M. Bellare, R. Canetti, and H. Krawczyk. Keying hash functions for message authentication. InProceedings of CRYPTO, pages 1–15, 1996

    work page 1996

  12. [12]

    Ben-Or, S

    M. Ben-Or, S. Goldwasser, J. Kilian, and A. Wigderson. Multi-prover interactive proofs: How to remove intractability assumptions. InProceedings of STOC, pages 113–131, 1988

    work page 1988

  13. [13]

    Ben-Sasson and A

    E. Ben-Sasson and A. Wigderson. Short proofs are narrow–resolution made simple.J. ACM, 48(2):149–169, 2001

    work page 2001

  14. [14]

    L. Blum, M. Shub, and S. Smale. On a theory of computation and complexity over the real numbers: Np-completeness, recursive functions and universal machines.Bull. Amer. Math. Soc., 21(1):1–46, 1986

    work page 1986

  15. [15]

    L. Blum, M. Shub, and S. Smale. On a theory of computation over the real numbers.Notices Amer. Math. Soc., 35(1):1–46, 1989

    work page 1989

  16. [16]

    M. Blum. A machine-independent theory of the complexity of recursive functions.J. ACM, 14 (2):322–336, 1967

    work page 1967

  17. [17]

    Bürgisser.Completeness and Reduction in Algebraic Complexity Theory

    P. Bürgisser.Completeness and Reduction in Algebraic Complexity Theory. Springer, 2009

    work page 2009

  18. [18]

    Bürgisser, M

    P. Bürgisser, M. Clausen, and M. A. Shokrollahi.Algebraic Complexity Theory. Springer, 1997

    work page 1997

  19. [19]

    C. S. Calude.Information and Randomness: An Algorithmic Perspective. Springer, 2002

    work page 2002

  20. [20]

    R. Canetti. Universally composable security: A new paradigm for cryptographic protocols. In Proceedings of FOCS, pages 136–145, 2001

    work page 2001

  21. [21]

    G. J. Chaitin. On the length of programs for computing finite binary sequences.J. ACM, 13 (4):547–569, 1966

    work page 1966

  22. [22]

    N. Chomsky. On certain formal properties of grammars.Information and Control, 2(2): 137–167, 1959

    work page 1959

  23. [23]

    A. Church. An unsolvable problem of elementary number theory.Amer. J. Math., 58(2): 345–363, 1936. 55

    work page 1936

  24. [24]

    A. Cobham. The intrinsic computational difficulty of functions. InProceedings of the 1964 International Congress for Logic, Methodology and Philosophy of Science, pages 24–30, 1964

    work page 1964

  25. [25]

    S. A. Cook. The complexity of theorem-proving procedures.Proceedings of STOC, pages 151–158, 1971

    work page 1971

  26. [26]

    S. A. Cook and R. A. Reckhow. The relative efficiency of propositional proof systems.J. Symbolic Logic, 44(1):36–50, 1979

    work page 1979

  27. [27]

    Cook and Robert A

    Stephen A. Cook and Robert A. Reckhow. The relative efficiency of propositional proof systems.Journal of Symbolic Logic, 44(1):36–50, 1979

    work page 1979

  28. [28]

    Cucker and S

    F. Cucker and S. Smale. On the mathematical foundations of learning.Bull. Amer. Math. Soc., 39(1):1–49, 2002

    work page 2002

  29. [29]

    R. G. Downey and D. R. Hirschfeldt.Algorithmic Randomness and Complexity. Springer, 2010

    work page 2010

  30. [30]

    Du and K

    D. Du and K. Ko.Theory of Computational Complexity. Wiley, 2000

    work page 2000

  31. [31]

    J. Edmonds. Paths, trees, and flowers.Canad. J. Math., 17:449–467, 1965

    work page 1965

  32. [32]

    L. Fortnow. The complexity of perfect zero-knowledge. InProceedings of STOC, pages 204–209, 1987

    work page 1987

  33. [33]

    Fortnow.Complexity-theoretic aspects of interactive proof systems

    L. Fortnow.Complexity-theoretic aspects of interactive proof systems. PhD thesis, MIT, 1989

    work page 1989

  34. [34]

    Fortnow.The Golden Ticket: P, NP, and the Search for the Impossible

    L. Fortnow.The Golden Ticket: P, NP, and the Search for the Impossible. Princeton University Press, 2013

    work page 2013

  35. [35]

    Fortnow and S

    L. Fortnow and S. Homer. A short history of computational complexity.Bull. EATCS, 80: 95–133, 2003

    work page 2003

  36. [36]

    Fortnow and A

    L. Fortnow and A. R. Klivans. Efficient learning algorithms yield circuit lower bounds.J. Comput. Syst. Sci., 75(1):27–36, 2009

    work page 2009

  37. [37]

    Fortnow and J

    L. Fortnow and J. Rompel. One-sided versus two-sided error in probabilistic computation. In Proceedings of STOC, pages 468–475, 1995

    work page 1995

  38. [38]

    Fortnow and M

    L. Fortnow and M. Sipser. Are there interactive protocols for co-np languages?Information Processing Letters, 28(5):249–251, 1988

    work page 1988

  39. [39]

    M. R. Garey and D. S. Johnson.Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979

    work page 1979

  40. [40]

    Goldreich.Foundations of Cryptography: Basic Tools

    O. Goldreich.Foundations of Cryptography: Basic Tools. Cambridge University Press, 2001

    work page 2001

  41. [41]

    Goldreich.Foundations of Cryptography: Basic Applications

    O. Goldreich.Foundations of Cryptography: Basic Applications. Cambridge University Press, 2004

    work page 2004

  42. [42]

    Goldreich.Computational Complexity: A Conceptual Perspective

    O. Goldreich.Computational Complexity: A Conceptual Perspective. Cambridge University Press, 2008

    work page 2008

  43. [43]

    Goldreich, S

    O. Goldreich, S. Micali, and A. Wigderson. Proofs that yield nothing but their validity or all languages in np have zero-knowledge proof systems.J. ACM, 38(3):690–728, 1991. 56

    work page 1991

  44. [44]

    Goldwasser and S

    S. Goldwasser and S. Micali. Probabilistic encryption.J. Comput. Syst. Sci., 28(2):270–299, 1984

    work page 1984

  45. [45]

    Goldwasser, S

    S. Goldwasser, S. Micali, and C. Rackoff. The knowledge complexity of interactive proof systems.SIAM J. Comput., 18(1):186–208, 1989

    work page 1989

  46. [46]

    Hartmanis and R

    J. Hartmanis and R. E. Stearns. On the computational complexity of algorithms.Trans. Amer. Math. Soc., 117:285–306, 1965

    work page 1965

  47. [47]

    Heintz and M

    J. Heintz and M. Sieveking. Lower bounds for polynomials with algebraic coefficients.Theor. Comput. Sci., 11(3):321–330, 1980

    work page 1980

  48. [48]

    J. E. Hopcroft and J. D. Ullman.Formal languages and their relation to automata. Addison- Wesley, 1969

    work page 1969

  49. [49]

    J. E. Hopcroft and J. D. Ullman.Introduction to Automata Theory, Languages, and Computa- tion. Addison-Wesley, 1979

    work page 1979

  50. [50]

    Structurally-aware turing machines: Transcending complexity barriers

    Rafig Huseynzade. Structurally-aware turing machines: Transcending complexity barriers. GitHub repository, 2025. URLhttps://github.com/Acloyer/SA-TM. SA-TM (oracle model) preprint on GitHub

    work page 2025

  51. [51]

    Immerman

    N. Immerman. Nondeterministic space is closed under complementation.SIAM J. Comput., 17(5):935–938, 1987

    work page 1987

  52. [52]

    Impagliazzo

    R. Impagliazzo. A personal view of average-case complexity.Proceedings of STOC, pages 134–147, 1995

    work page 1995

  53. [53]

    Impagliazzo

    R. Impagliazzo. Relativized separations of worst-case and average-case complexities. In Proceedings of CCC, pages 108–117, 2001

    work page 2001

  54. [54]

    Impagliazzo and A

    R. Impagliazzo and A. Wigderson. Derandomizing the polynomial hierarchy if bpp has subexponential circuits. InProceedings of STOC, pages 191–200, 2002

    work page 2002

  55. [55]

    Kabanets and R

    V. Kabanets and R. Impagliazzo. Derandomizing polynomial identity tests means proving circuit lower bounds. InProceedings of STOC, pages 355–364, 2003

    work page 2003

  56. [56]

    R. M. Karp. Reducibility among combinatorial problems. InComplexity of Computer Computations, pages 85–103, 1972

    work page 1972

  57. [57]

    R. M. Karp. On the complexity of combinatorial problems: Recent results and new directions. InProceedings of IFIP Congress, pages 1–15, 1974

    work page 1974

  58. [58]

    R. M. Karp. The probabilistic analysis of some combinatorial search algorithms. InAlgorithms and Complexity: New Directions and Recent Results, pages 1–19, 1976

    work page 1976

  59. [59]

    R. M. Karp and M. O. Rabin. Efficient randomized pattern-matching algorithms.IBM J. Res. Dev., 31(2):249–260, 1987

    work page 1987

  60. [60]

    R. M. Karp and V. Ramachandran. Parallel algorithms for shared-memory machines. In Handbook of Theoretical Computer Science, pages 869–941, 1990

    work page 1990

  61. [61]

    R. M. Karp and R. E. Tarjan. Linear expected-time algorithms for connectivity problems.J. Algorithms, 8(3):374–381, 1987. 57

    work page 1987

  62. [62]

    R. M. Karp and A. Wigderson. A fast parallel algorithm for the maximal independent set problem.J. ACM, 32(4):762–773, 1985

    work page 1985

  63. [63]

    R. M. Karp, E. Upfal, and A. Wigderson. Constructing a perfect matching is in random nc. Combinatorica, 6(1):35–48, 1986

    work page 1986

  64. [64]

    R. M. Karp, E. Upfal, and A. Wigderson. The complexity of parallel search.J. Comput. Syst. Sci., 36(2):225–253, 1988

    work page 1988

  65. [65]

    Katz and Y

    J. Katz and Y. Lindell.Introduction to Modern Cryptography. CRC Press, 2014

    work page 2014

  66. [66]

    S. C. Kleene. Recursive predicates and quantifiers.Trans. Amer. Math. Soc., 53(1):41–73, 1943

    work page 1943

  67. [67]

    A. N. Kolmogorov. Three approaches to the quantitative definition of information.Problems of Information Transmission, 1(1):1–7, 1965

    work page 1965

  68. [68]

    Kozen.Theory of Computation

    D. Kozen.Theory of Computation. Springer, 2006

    work page 2006

  69. [69]

    R. E. Ladner. On the structure of polynomial time reducibility.J. ACM, 22(1):155–171, 1975

    work page 1975

  70. [70]

    L. A. Levin. Universal sequential search problems.Problems of Information Transmission, 9 (3):265–266, 1973

    work page 1973

  71. [71]

    L. A. Levin. Randomness conservation inequalities; information and independence in mathe- matical theories.Information and Control, 61(1):15–37, 1984

    work page 1984

  72. [72]

    H. R. Lewis and C. H. Papadimitriou.Elements of the Theory of Computation. Prentice-Hall, 1981

    work page 1981

  73. [73]

    Li and P

    M. Li and P. M. B. Vitányi.An Introduction to Kolmogorov Complexity and Its Applications. Springer, 2008

    work page 2008

  74. [74]

    C. Lund, L. Fortnow, H. Karloff, and N. Nisan. Algebraic methods for interactive proof systems.J. ACM, 39(4):859–868, 1992

    work page 1992

  75. [75]

    A. A. Markov. On the impossibility of certain algorithms in the theory of associative systems. Dokl. Akad. Nauk SSSR, 55(7):583–586, 1947

    work page 1947

  76. [76]

    Martin-Löf

    P. Martin-Löf. The definition of random sequences.Information and Control, 9(6):602–619, 1966

    work page 1966

  77. [77]

    W. S. McCulloch and W. Pitts. A logical calculus of the ideas immanent in nervous activity. Bull. Math. Biophys., 5(4):115–133, 1943

    work page 1943

  78. [78]

    J. Myhill. Finite automata and the representation of events. Technical Report 57–624, WADD Technical Report, 1956

    work page 1956

  79. [79]

    A. Nerode. Linear automaton transformations.Proc. Amer. Math. Soc., 9(4):541–544, 1958

    work page 1958

  80. [80]

    Nies.Computability and Randomness

    A. Nies.Computability and Randomness. Oxford University Press, 2009

    work page 2009

Showing first 80 references.