E-complete sets do not have optimal polynomial time approximations

DOI10.1007/3-540-58338-6_57zbMath1494.68090OpenAlexW1545923104MaRDI QIDQ5096868

Pavol Ďuriš, José D. P. Rolim

Publication date: 18 August 2022

Published in: Mathematical Foundations of Computer Science 1994 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-58338-6_57

Mathematics Subject Classification ID

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

Related Items (2)

On optimal polynomial time approximations: P-levelability vs. δ-levelability ⋮ Genericity, Randomness, and Polynomial-Time Approximations

Cites Work

• On one-one polynomial time equivalence relations
• On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets
• Bi-immune sets for complexity classes
• Optimal Approximations and Polynomially Levelable Sets
• Completeness, Approximation and Density
• Unnamed Item

This page was built for publication: E-complete sets do not have optimal polynomial time approximations