On lower bounds of the closeness between complexity classes

DOI10.1007/BF01202282zbMath0771.68050OpenAlexW2073777163MaRDI QIDQ4032931

Bin Fu

Publication date: 17 May 1993

Published in: Mathematical Systems Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01202282

zbMATH Keywords

lower boundstructural complexitycloseness of approximationdensity of the symmetric difference

Mathematics Subject Classification ID

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

Related Items (5)

Separating NE from Some Nonuniform Nondeterministic Complexity Classes ⋮ Separating NE from some nonuniform nondeterministic complexity classes ⋮ The fault tolerance of NP-hard problems ⋮ The Fault Tolerance of NP-Hard Problems ⋮ On symmetric differences of NP-hard sets with weakly P-selective sets

Cites Work

• Probabilistic complexity classes and lowness
• On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets
• PP is as Hard as the Polynomial-Time Hierarchy
• On Sets Truth-Table Reducible to Sparse Sets
• Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
• Complete Problems and Strong Polynomial Reducibilities
• Complete sets and closeness to complexity classes

This page was built for publication: On lower bounds of the closeness between complexity classes