On optimal polynomial time approximations: P-levelability vs. δ-levelability

DOI10.1007/3-540-60084-1_90zbMath1412.68074OpenAlexW56605959MaRDI QIDQ4645194

Ambos-Spies, Klaus

Publication date: 10 January 2019

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-60084-1_90

zbMATH Keywords

polynomial approximationTuring machineoptimal approximationpolynomial timelevelability concept

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (1)

Genericity, Randomness, and Polynomial-Time Approximations

Cites Work

• Unnamed Item
• Unnamed Item
• 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
• E-complete sets do not have optimal polynomial time approximations

This page was built for publication: On optimal polynomial time approximations: P-levelability vs. δ-levelability