@article {Agrawal:October 1998:0022-0000:127,
	author = "Agrawal M.",
	author = "Allender E.",
	author = "Rudich S.",
	title = "Reductions in Circuit Complexity: An Isomorphism Theorem and a Gap Theorem",
	journal = "Journal of Computer and System Sciences",
	volume = "57",
	year = "October 1998",
	abstract = "<P>We show that all sets that are complete for NP under nonuniform <B>AC</B><SUP>0</SUP> reductions are isomorphic under nonuniform <B>AC</B><SUP>0</SUP>-computable isomorphisms. Furthermore, these sets remain NP-complete even under nonuniform <B>NC</B><SUP>0</SUP> reductions. More generally, we show two theorems that hold for any complexity class <IMG SRC="/iso-ents/isomscr/cscr-c.gif" ALT="Cscr"> closed under (uniform) <B>NC</B><SUP>1</SUP>-computable many&#150;one reductions. <B><I>Gap</B></I>: The sets that are complete for <IMG SRC="/iso-ents/isomscr/cscr-c.gif" ALT="Cscr"> under<B>AC</B><SUP>0</SUP> and <B>NC</B><SUP>0</SUP> reducibility coincide. <B><I>Isomorphism</B></I>: The sets complete for <IMG SRC="/iso-ents/isomscr/cscr-c.gif" ALT="Cscr"> under <B>AC</B><SUP>0</SUP> reductions are all isomorphic under isomorphisms computable and invertible by <B>AC</B><SUP>0</SUP> circuits of depth three. Our Gap Theorem does not hold for strongly uniform reductions; we show that there are Dlogtime-uniform <B>AC</B><SUP>0</SUP>-complete sets for <B>NC</B><SUP>1</SUP> that are not Dlogtime-uniform <B>NC</B><SUP>0</SUP>-complete.<B> Copyright 1998 Academic Press.</B></P>",
	pages = "127-143(17)",
	url = "http://www.ingentaconnect.com/content/ap/ss/1998/00000057/00000002/art01583"
}