Structural properties of bounded relations with an application to NP optimization problems

DOI10.1016/S0304-3975(99)00121-8MaRDI QIDQ1589424zbMATH OpenFDO

Authors Wolfgang Merkle

Publication date 12 December 2000

Published in Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

lattice embeddingspartial order embeddingsabstract reducibilitiesapproximation preserving reducibilitiesnon-uniform reducibilitiesresource bounded reducibilities

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• scientific article; zbMATH DE number 4126690
• scientific article; zbMATH DE number 515727
• Structure in Approximation Classes
• Logical definability of NP optimization problems
• Lattice embeddings for abstract bounded reducibilities

Cites work

• scientific article; zbMATH DE number 2077131 (Why is no real title available?)
• scientific article; zbMATH DE number 1559517 (Why is no real title available?)
• A uniform approach to obtain diagonal sets in complexity classes
• An observation on probability versus randomness with applications to complexity classes
• Completeness in approximation classes
• Lattice embeddings for abstract bounded reducibilities
• Minimal pairs for P
• On Syntactic versus Computational Views of Approximability
• On the Structure of Polynomial Time Reducibility
• On the structure of sets in NP and other complexity classes
• Optimization, approximation, and complexity classes
• Polynomial and abstract subrecursive classes
• Sublattices of the polynomial time degrees
• The recursion-theoretic structure of complexity classes

This page was built for publication: Structural properties of bounded relations with an application to NP optimization problems

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