Forcing complexity: Minimum sizes of forcing conditions.

DOI10.1305/NDJFL/1054837938MaRDI QIDQ1409312zbMATH OpenOpenAlexFDO

Authors Toshio Suzuki

Publication date 13 October 2003

Published in Notre Dame Journal of Formal Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1305/ndjfl/1054837938

zbMATH Keywords

computational complexity\(t\)-generic oracles

Mathematics Subject Classification ID

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

Recommendations

• Complexity of the \(r\)-query tautologies in the presence of a generic oracle
• Computable Dowd-type generic oracles
• Degrees of Dowd-type generic oracles
• Generic oracles, uniform machines, and codes
• The generic oracle hypothesis is false

Cites work

• scientific article; zbMATH DE number 3950504 (Why is no real title available?)
• scientific article; zbMATH DE number 1294498 (Why is no real title available?)
• Complexity of the \(r\)-query tautologies in the presence of a generic oracle
• Degrees of Dowd-type generic oracles
• Generic oracles, uniform machines, and codes
• Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1

Cited in

(5)

• Degrees of Dowd-type generic oracles
• Resource-bounded martingales and computable Dowd-type generic sets
• Bounded truth table does not reduce the one-query tautologies to a random oracle
• Computable Dowd-type generic oracles
• Does truth-table of linear norm reduce the one-query tautologies to a random oracle?

This page was built for publication: Forcing complexity: Minimum sizes of forcing conditions.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1409312)