On Approximability of Boolean Formula Minimization期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

按检索

On Approximability of Boolean Formula Minimization

Authors:	Oleg A Prokopyev Panos M Pardalos

Institution:	(1) Department of Industrial and Systems Engineering, University of Florida, Gainesvillw, 32611, FL, USA

Abstract:	For a Boolean function $f:\left\{ {0,1} \right\}^n \to \left\{ {0,1} \right\}$ 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., $Pr_{x \in \left\{ {0,1} \right\}^n } \left\{ {g\left( x \right) \ne f\left( x \right)} \right\} \leqslant \varepsilon$ . 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 等数据库收录！