Does truth-table of linear norm reduce the one-query tautologies to a random oracle?
Publication:948913
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
computational complexitytruth-table reductionrandom oracleforcing complexitymonotone Boolean formula
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)
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?
