Generic oracles, uniform machines, and codes

DOI10.1016/0890-5401(92)90055-KzbMath0755.68052MaRDI QIDQ1184732

Martin Dowd

Publication date: 28 June 1992

Published in: Information and Computation (Search for Journal in Brave)

zbMATH Keywords

circuitstautologiesgeneric oracles

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (9)

11th Asian Logic Conference ⋮ Bounded truth table does not reduce the one-query tautologies to a random oracle ⋮ Forcing complexity: Minimum sizes of forcing conditions. ⋮ Strong self-reducibility precludes strong immunity ⋮ Does truth-table of linear norm reduce the one-query tautologies to a random oracle? ⋮ 10th Asian Logic Conference ⋮ Degrees of Dowd-type generic oracles ⋮ Resource-bounded martingales and computable Dowd-type generic sets ⋮ Complexity of the \(r\)-query tautologies in the presence of a generic oracle

Cites Work

• Unnamed Item
• Unnamed Item
• Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
• A Theory of Program Size Formally Identical to Information Theory
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• Log Space Recognition and Translation of Parenthesis Languages
• Relations Among Complexity Measures
• Hilbert's Tenth Problem is Unsolvable
• Some applications of the notions of forcing and generic sets
• On the Length of Programs for Computing Finite Binary Sequences
• Some applications of forcing to hierarchy problems in arithmetic

This page was built for publication: Generic oracles, uniform machines, and codes