scientific article; zbMATH DE number 4099277

MaRDI QIDQ3824299zbMATH OpenFDO

Authors Marius Zimand

Publication date 1988

zbMATH Keywords

complexity classesoraclerelativizationTuring machine

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Other degrees and reducibilities in computability and recursion theory (03D30) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Positive Relativizations of Complexity Classes
• Relativizing relativized computations
• Publication:3030806
• scientific article; zbMATH DE number 4011940
• Positive relativizations of the \(P=?\) NP problem

Cited in

(14)

• Complexity classes without machines: on complete languages for UP
• On the relative complexity of hard problems for complexity classes without complete problems
• Positive relativizations of the \(P=?\) NP problem
• Positive versions of polynomial time
• Relativizing relativized computations
• scientific article; zbMATH DE number 4019036 (Why is no real title available?)
• Positive Relativizations of Complexity Classes
• Relative Pfaffian closure for definably complete Baire structures
• On complete problems, relativizations and logics for complexity classes
• On relativizations with restricted number of accesses to the oracle set
• scientific article; zbMATH DE number 14489 (Why is no real title available?)
• On existence of complete sets for bounded reducibilities
• scientific article; zbMATH DE number 866668 (Why is no real title available?)
• Observations on complete sets between linear time and polynomial time

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 Q3824299)