|
|||||
|
|
On Approximability of Boolean Formula Minimization |
|
| Authors: | Oleg A. Prokopyev Panos M. Pardalos |
| Affiliation: | (1) Department of Industrial and Systems Engineering, University of Florida, Gainesvillw, 32611, FL, USA |
| Abstract: | For a Boolean function  given by a Boolean formula (or a binary circuit) S we discuss the problem of building a Boolean formula (binary circuit) of minimal size, which computes the function g equivalent to  , or  -equivalent to  , i.e.,  . In this paper we prove that if P  NP then this problem can not be approximated with a  good approximation ratio by a polynomial time algorithm. |
| Keywords: | minimum formula size problem minimum circuit size problem approximation Boolean circuits Boolean formulas inapproximability combinatorial optimization |
| 本文献已被 SpringerLink 等数据库收录！ | |