Nonuniform lowness and strong nonuniform lowness

DOI10.1007/BF02943492zbMath0837.68036OpenAlexW2002271852MaRDI QIDQ1894328

Guanying Li, Hong-zhou Li

Publication date: 27 August 1995

Published in: Journal of Computer Science and Technology (Search for Journal in Brave)

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

zbMATH Keywords

sparse setspolynomial-time hierarchystrong nonuniform lowness

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Some consequences of non-uniform conditions on uniform classes
• A low and a high hierarchy within NP
• Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
• The polynomial-time hierarchy and sparse oracles
• On Circuit-Size Complexity and the Low Hierarchy in NP
• Sparse Sets, Lowness and Highness
• Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets

This page was built for publication: Nonuniform lowness and strong nonuniform lowness