Turing machines that take advice

zbMath0529.68025MaRDI QIDQ787674

Richard J. Lipton, Richard M. Karp

Publication date: 1982

Published in: L'Enseignement Mathématique. 2e Série (Search for Journal in Brave)

zbMATH Keywords

uniform measurenon-uniform complexity classnon-uniform complexity measuresreducibility among complexity classesuniform complexity class

Mathematics Subject Classification ID

Related Items (76)

In search of an easy witness: Exponential time vs. probabilistic polynomial time. ⋮ On reductions of NP sets to sparse sets ⋮ Analog computation via neural networks ⋮ Hardness vs randomness ⋮ Two-way non-uniform finite automata ⋮ Separation of complexity classes in Koiran's weak model ⋮ The complexity of planarity testing ⋮ Multiple Usage of Random Bits in Finite Automata ⋮ Some complete and intermediate polynomials in algebraic complexity theory ⋮ Unnamed Item ⋮ Quasi-linear truth-table reductions to \(p\)-selective sets ⋮ Relating the bounded arithmetic and polynomial time hierarchies ⋮ Self-reducibility ⋮ Polynomial time quantum computation with advice ⋮ \(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\) ⋮ Nonuniform reductions and NP-completeness ⋮ Kolmogorov complexity descriptions of the exquisite behaviors of advised deterministic pushdown automata ⋮ An observation on probability versus randomness with applications to complexity classes ⋮ A Note on polynomial-size circuits with low resource-bounded Kolmogorov complexity ⋮ Robust simulations and significant separations ⋮ On the Limit of Some Algorithmic Approach to Circuit Lower Bounds ⋮ On complexity classes and algorithmically random languages ⋮ Inductive counting below logspace ⋮ Reactive Turing machines ⋮ Infeasibility of instance compression and succinct PCPs for NP ⋮ Question answering by humans and machines: a complexity-theoretic view ⋮ Effective guessing has unlikely consequences ⋮ How We Think of Computing Today ⋮ Determinism and Nondeterminism in Finite Automata with Advice ⋮ Two-Way Non-Uniform Finite Automata ⋮ Unambiguity and fewness for nonuniform families of polynomial-size nondeterministic finite automata ⋮ A note on the self-witnessing property of computational problems ⋮ Catalytic space: non-determinism and hierarchy ⋮ \(P^{NP[O(\log n)}\) and sparse turing-complete sets for NP] ⋮ Interpolation in Valiant's theory ⋮ Amount of nonconstructivity in deterministic finite automata ⋮ Circuit Lower Bounds for Nondeterministic Quasi-polytime from a New Easy Witness Lemma ⋮ Extensional Uniformity for Boolean Circuits ⋮ Two-way automata making choices only at the endmarkers ⋮ One-way reversible and quantum finite automata with advice ⋮ On the computational power of discrete Hopfield nets ⋮ In defense of PDDL axioms ⋮ Lower bounds against weakly-uniform threshold circuits ⋮ Towards efficient universal planning: A randomized approach ⋮ State complexity characterizations of parameterized degree-bounded graph connectivity, sub-linear space computation, and the linear space hypothesis ⋮ Optimal advice ⋮ On the Amount of Nonconstructivity in Learning Recursive Functions ⋮ On the complexity of existential positive queries ⋮ Extensions to Barrington's M-program model ⋮ Two-way unary automata versus logarithmic space ⋮ Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games ⋮ Fourier concentration from shrinkage ⋮ Complexity classes of equivalence problems revisited ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Large finite structures with few \(L^k\)-types ⋮ Nonuniform families of polynomial-size quantum finite automata and quantum logarithmic-space computation with polynomial-size advice ⋮ Boolean functional synthesis: hardness and practical algorithms ⋮ On the amount of nonconstructivity in learning formal languages from text ⋮ On hiding information from an oracle ⋮ Amount of Nonconstructivity in Finite Automata ⋮ On sets bounded truth-table reducible to $P$-selective sets ⋮ Relations and equivalences between circuit lower bounds and karp-lipton theorems ⋮ Boolean operations, joins, and the extended low hierarchy ⋮ Unnamed Item ⋮ Sparse hard sets for P: Resolution of a conjecture of Hartmanis ⋮ Resolution of Hartmanis' conjecture for NL-hard sparse sets ⋮ Theory of one-tape linear-time Turing machines ⋮ Advice hierarchies among finite automata ⋮ Saturation and stability in the theory of computation over the reals ⋮ On the typical case complexity of graph optimization ⋮ Unnamed Item ⋮ Real computations with fake numbers ⋮ Randomness vs time: Derandomization under a uniform assumption ⋮ Synthesis of succinct systems ⋮ Multi-head finite automata: Data-independent versus data-dependent computations

This page was built for publication: Turing machines that take advice