Bounded truth table does not reduce the one-query tautologies to a random oracle

DOI10.1007/s00153-005-0283-1zbMath1087.03024OpenAlexW2070778117MaRDI QIDQ2388434

Toshio Suzuki

Publication date: 13 September 2005

Published in: Archive for Mathematical Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00153-005-0283-1

zbMATH Keywords

measurerandom oracleDowd-type generic oracleone-query tautologypolynomial-time btt reductionrelativized propositional calculustruth table reduction

Mathematics Subject Classification ID

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

Related Items (2)

Does truth-table of linear norm reduce the one-query tautologies to a random oracle? ⋮ Resource-bounded martingales and computable Dowd-type generic sets

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Diagonalizations over polynomial time computable sets
• Some observations on the probabilistic algorithms and NP-hard problems
• Generic oracles, uniform machines, and codes
• A comparison of polynomial time reducibilities
• Genericity and measure for exponential time
• Forcing complexity: Minimum sizes of forcing conditions.
• Degrees of Dowd-type generic oracles
• Complexity of the \(r\)-query tautologies in the presence of a generic oracle
• Polynomial-time reducibilities and ``almost all oracle sets
• Measure-theoretic construction of incomparable hyperdegrees
• On the random oracle hypothesis
• Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
• Degrees of Unsolvability. (AM-55)

This page was built for publication: Bounded truth table does not reduce the one-query tautologies to a random oracle