Does truth-table of linear norm reduce the one-query tautologies to a random oracle? (Q948913): Difference between revisions

@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1007/s00153-008-0076-4
+Normal rank
@@ Property / OpenAlex ID @@
+W2037563943
@@ Property / OpenAlex ID: W2037563943 / rank @@
+Normal rank
@@ Property / cites work @@
+What can be efficiently reduced to the Kolmogorov-random strings?
+Normal rank
@@ Property / cites work @@
+Q4723714
@@ Property / cites work: Q4723714 / rank @@
+Normal rank
@@ Property / cites work @@
+Diagonalizations over polynomial time computable sets
+Normal rank
@@ Property / cites work @@
+Q4348122
@@ Property / cites work: Q4348122 / rank @@
+Normal rank
@@ Property / cites work @@
+Genericity and measure for exponential time
@@ Property / cites work: Genericity and measure for exponential time / rank @@
+Normal rank
@@ Property / cites work @@
+Q4039803
@@ Property / cites work: Q4039803 / rank @@
+Normal rank
@@ Property / cites work @@
+Relative to a Random Oracle<i>A</i>, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
+Normal rank
@@ Property / cites work @@
+Generic oracles, uniform machines, and codes
@@ Property / cites work: Generic oracles, uniform machines, and codes / rank @@
+Normal rank
@@ Property / cites work @@
+Calibrating Randomness
@@ Property / cites work: Calibrating Randomness / rank @@
+Normal rank
@@ Property / cites work @@
+Some observations on the probabilistic algorithms and NP-hard problems
+Normal rank
@@ Property / cites work @@
+Does truth-table of linear norm reduce the one-query tautologies to a random oracle?
+Normal rank
@@ Property / cites work @@
+A comparison of polynomial time reducibilities
@@ Property / cites work: A comparison of polynomial time reducibilities / rank @@
+Normal rank
@@ Property / cites work @@
+Recursively enumerable sets of positive integers and their decision problems
+Normal rank
@@ Property / cites work @@
+Q5573961
@@ Property / cites work: Q5573961 / rank @@
+Normal rank
@@ Property / cites work @@
+Degrees of Unsolvability. (AM-55)
@@ Property / cites work: Degrees of Unsolvability. (AM-55) / rank @@
+Normal rank
@@ Property / cites work @@
+Q4246600
@@ Property / cites work: Q4246600 / rank @@
+Normal rank
@@ Property / cites work @@
+Complexity of the \(r\)-query tautologies in the presence of a generic oracle
+Normal rank
@@ Property / cites work @@
+Forcing complexity: Minimum sizes of forcing conditions.
+Normal rank
@@ Property / cites work @@
+Degrees of Dowd-type generic oracles
@@ Property / cites work: Degrees of Dowd-type generic oracles / rank @@
+Normal rank
@@ Property / cites work @@
+Bounded truth table does not reduce the one-query tautologies to a random oracle
+Normal rank
@@ Property / cites work @@
+Polynomial-time reducibilities and ``almost all'' oracle sets
+Normal rank
@@ Property / DBLP publication ID @@
+journals/aml/KumabeSY08
@@ Property / DBLP publication ID: journals/aml/KumabeSY08 / rank @@
+Normal rank