scientific article; zbMATH DE number 841081

MaRDI QIDQ4863237zbMATH OpenFDO

Authors Klaus Ambos-Spies

Publication date 4 February 1996

zbMATH Keywords

diagonalizationpolynomial timegeneric setsco-meager set

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• scientific article; zbMATH DE number 3885884
• scientific article; zbMATH DE number 1492083
• Finite-state genericity. On the diagonalization strength of finite automata.
• Diagonalizations over polynomial time computable sets
• scientific article; zbMATH DE number 2040942

Cited in

(13)

• Degrees of Dowd-type generic oracles
• An oracle builder's toolkit
• Comparing nontriviality for E and EXP
• Special issue: 17th ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, Seattle, WA, USA, June 1--3, 1998
• scientific article; zbMATH DE number 2040942 (Why is no real title available?)
• Resource bounded randomness and weakly complete problems
• Dynamic notions of genericity and array noncomputability
• Bounded truth table does not reduce the one-query tautologies to a random oracle
• Diagonalizations over polynomial time computable sets
• Genericity and randomness over feasible probability measures
• Weak completeness notions for exponential time
• Finite-state genericity. On the diagonalization strength of finite automata.
• Resource-bounded strong dimension versus resource-bounded category

This page was built for publication:

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