Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > BERMAN-HARTMANIS CONJECTURE:
Reports tagged with Berman-Hartmanis Conjecture:
TR96-002 | 10th January 1996
Manindra Agrawal, Eric Allender

#### An Isomorphism Theorem for Circuit Complexity

We show that all sets complete for NC\$^1\$ under AC\$^0\$
reductions are isomorphic under AC\$^0\$-computable isomorphisms.

Although our proof does not generalize directly to other
complexity classes, we do show that, for all complexity classes C
closed under NC\$^1\$-computable many-one reductions, the sets ... more >>>

TR16-162 | 18th October 2016
Joshua Grochow

#### NP-hard sets are not sparse unless P=NP: An exposition of a simple proof of Mahaney's Theorem, with applications

Mahaney's Theorem states that, assuming P \$\neq\$ NP, no NP-hard set can have a polynomially bounded number of yes-instances at each input length. We give an exposition of a very simple unpublished proof of Manindra Agrawal whose ideas appear in Agrawal-Arvind ("Geometric sets of low information content," Theoret. Comp. Sci., ... more >>>

ISSN 1433-8092 | Imprint