ECCC-Report TR05-127https://eccc.weizmann.ac.il/report/2005/127Comments and Revisions published for TR05-127en-usWed, 10 Sep 2008 00:00:00 +0300
Revision 1
| Hardness of Approximate Two-level Logic Minimization and PAC Learning with Membership Queries |
Vitaly Feldman
https://eccc.weizmann.ac.il/report/2005/127#revision1Producing a small DNF expression consistent with given data is a classical problem in computer science that occurs in a number of forms and has numerous applications. We consider two standard variants of this problem. The first one is two-level logic minimization or finding a minimum DNF formula consistent with a given complete truth table (TT-MINDNF). This problem was formulated by Quine in 1952 and has been since one of the key problems in logic design. It was proved NP-complete by Masek in 1979.
The best known polynomial approximation algorithm is based on a reduction to the SET-COVER problem and produces a DNF formula of size $O(d\cdot \mbox{OPT})$, where $d$ is the number of variables. We prove that TT-MINDNF is NP-hard to approximate within $d^\gamma$ for some constant $\gamma > 0$, establishing the first inapproximability result for the problem.
The other DNF minimization problem we consider is PAC learning of DNF expressions when the learning algorithm must output a DNF expression as its hypothesis (referred to as proper learning). We prove that DNF expressions are NP-hard to PAC learn properly even when the learner has access to membership queries, thereby answering a long-standing Valiant's open question (1984). Finally, we provide a concrete connection between these variants of DNF minimization problem. Specifically, we prove that inapproximability of TT-MINDNF implies hardness results for restricted proper learning of DNF expressions with membership queries even when learning with respect to the uniform distribution only.
Wed, 10 Sep 2008 00:00:00 +0300https://eccc.weizmann.ac.il/report/2005/127#revision1
Paper TR05-127
| Hardness of Approximate Two-level Logic Minimization and PAC Learning with Membership Queries |
Vitaly Feldman
https://eccc.weizmann.ac.il/report/2005/127Producing a small DNF expression consistent with given data is a
classical problem in computer science that occurs in a number of forms and
has numerous applications. We consider two standard variants of this
problem. The first one is two-level logic minimization or finding a minimal
DNF formula consistent with a given complete truth table (MinDNF). This
problem was formulated by Quine in 1952 and has been since one of the key
problems in logic design. It was proved NP-complete by Masek in 1979.
The best known polynomial approximation algorithm is based on a reduction to
the SET-COVER problem and produces a DNF formula of size $O(d \cdot OPT)$,
where $d$ is the number of variables. We prove that MinDNF is NP-hard to
approximate within $d^\gamma$ for some constant $\gamma > 0$, establishing
the first inapproximability result for the problem.
The other DNF minimization problem we consider is PAC learning of DNF
expressions when the learning algorithm must output a DNF expression as its
hypothesis (referred to as proper learning). We prove that DNF expressions
are NP-hard to PAC learn properly even when the learner has access to
membership queries, thereby answering a long-standing open question due to
Valiant \cite{Valiant:84}. Finally, we observe that inapproximability of
MinDNF implies hardness results for restricted proper learning of DNF
expressions with membership queries even when learning with respect to the
uniform distribution only.
Sat, 05 Nov 2005 02:30:16 +0200https://eccc.weizmann.ac.il/report/2005/127