Does truth-table of linear norm reduce the one-query tautologies to a random oracle?

DOI10.1007/s00153-008-0076-4zbMath1149.68031DBLPjournals/aml/KumabeSY08OpenAlexW2037563943WikidataQ56460197 ScholiaQ56460197MaRDI QIDQ948913

Takeshi Yamazaki, Toshio Suzuki, Masahiro Kumabe

Publication date: 16 October 2008

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

Full work available at URL: https://doi.org/10.1007/s00153-008-0076-4

zbMATH Keywords

computational complexitytruth-table reductionrandom oracleforcing complexitymonotone Boolean formula

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Other degrees and reducibilities in computability and recursion theory (03D30)

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
• Does truth-table of linear norm reduce the one-query tautologies to a random oracle?
• 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
• Bounded truth table does not reduce the one-query tautologies to a random oracle
• What can be efficiently reduced to the Kolmogorov-random strings?
• Polynomial-time reducibilities and ``almost all oracle sets
• Calibrating Randomness
• 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)
• Recursively enumerable sets of positive integers and their decision problems

This page was built for publication: Does truth-table of linear norm reduce the one-query tautologies to a random oracle?