Lattice Embeddings for Abstract Bounded Reducibilities

DOI10.1137/S0097539701385958zbMath1010.03030MaRDI QIDQ2784495

Wolfgang Merkle

Publication date: 23 April 2002

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

resource-bounded reducibilitiesabstract reducibilitiesembeddings of distributive latticesembeddings of partial orderings

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Other degrees and reducibilities in computability and recursion theory (03D30) Theory of numerations, effectively presented structures (03D45) Abstract and axiomatic computability and recursion theory (03D75)

Related Items (2)

Canonical disjoint NP-pairs of propositional proof systems ⋮ Structural properties of bounded relations with an application to NP optimization problems

This page was built for publication: Lattice Embeddings for Abstract Bounded Reducibilities