loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
21st Annual IEEE Conference on Computational Complexity (CCC'06)
Minimizing DNF Formulas and AC^0_d Circuits Given a Truth Table
Prague, Czech Republic
July 16-July 20
ISBN: 0-7695-2596-2
ASCII Text
x 
 
Eric Allender, Lisa Hellerstein, Paul McCabe, Toniann Pitassi, Michael Saks, "Minimizing DNF Formulas and AC^0_d Circuits Given a Truth Table," Computational Complexity, Annual IEEE Conference on, pp. 237-251, 21st Annual IEEE Conference on Computational Complexity (CCC'06), 2006.
 
 
BibTex
x
 
@article{ 10.1109/CCC.2006.27,
author = {Eric Allender and Lisa Hellerstein and Paul McCabe and Toniann Pitassi and Michael Saks},
title = {Minimizing DNF Formulas and AC^0_d Circuits Given a Truth Table},
journal ={Computational Complexity, Annual IEEE Conference on},
volume = {0},
year = {2006},
issn = {1093-0159},
pages = {237-251},
doi = {http://doi.ieeecomputersociety.org/10.1109/CCC.2006.27},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Computational Complexity, Annual IEEE Conference on
TI - Minimizing DNF Formulas and AC^0_d Circuits Given a Truth Table
SN - 1093-0159
SP237
EP251
A1 - Eric Allender,
A1 - Lisa Hellerstein,
A1 - Paul McCabe,
A1 - Toniann Pitassi,
A1 - Michael Saks,
PY - 2006
KW - null
VL - 0
JA - Computational Complexity, Annual IEEE Conference on
ER -
 
Eric Allender, Rutgers University, USA
Lisa Hellerstein, Polytechnic University, USA
Paul McCabe, University of Toronto, Canada
Toniann Pitassi, University of Toronto, Canada
Michael Saks, Rutgers University, USA
For circuit classes R, the fundamental computational problem Min-R asks for the minimum R-size of a Boolean function presented as a truth table. Prominent examples of this problem include Min-DNF, which asks whether a given Boolean function presented as a truth table has a k-term DNF, and Min-Circuit (also called MCSP), which asks whether a Boolean function presented as a truth table has a size k Boolean circuit. We present a new reduction proving that Min-DNF is NP-complete. It is significantly simpler than the known reduction of Masek [31], which is from Circuit-SAT.
Citation:
Eric Allender, Lisa Hellerstein, Paul McCabe, Toniann Pitassi, Michael Saks, "Minimizing DNF Formulas and AC^0_d Circuits Given a Truth Table," ccc, pp.237-251, 21st Annual IEEE Conference on Computational Complexity (CCC'06), 2006
Usage of this product signifies your acceptance of the Terms of Use.