Forcing complexity: Minimum sizes of forcing conditions.

DOI10.1305/ndjfl/1054837938zbMath1060.03065OpenAlexW2060372513MaRDI QIDQ1409312

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 of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (3)

Bounded truth table does not reduce the one-query tautologies to a random oracle ⋮ 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

• Generic oracles, uniform machines, and codes
• Degrees of Dowd-type generic oracles
• Complexity of the \(r\)-query tautologies in the presence of a generic oracle
• Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
• Unnamed Item
• Unnamed Item

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