Loading...
Please wait, while we are loading the content...
Similar Documents
Hardness of Approximate Two-level Logic Minimization and PAC Learning with Membership Queries (2006)
| Content Provider | CiteSeerX |
|---|---|
| Author | Feldman, Vitaly |
| Description | Producing 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 · OPT), where d is the number of variables. We prove that TT-MinDNF is NP-hard to approximate within d γ for some constant γ> 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 [40]. 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. |
| File Format | |
| Language | English |
| Publisher | ACM Press |
| Publisher Date | 2006-01-01 |
| Publisher Institution | in Proceedings of the 38th Annual ACM Symposium on the Theory of Computing |
| Access Restriction | Open |
| Subject Keyword | Small Dnf Expression Consistent Numerous Application Set-cover Problem Known Polynomial Approximation Algorithm Concrete Connection Restricted Proper Learning Computer Science Approximate Two-level Logic Minimization Pac Learning Membership Query Key Problem Dnf Minimization Problem Minimum Dnf Formula Consistent Proper Learning Standard Variant Tt-mindnf Implies Hardness Result Dnf Formula Logic Design Learning Algorithm Two-level Logic Minimization Classical Problem Long-standing Open Question Complete Truth Table First Inapproximability Result Dnf Expression Uniform Distribution |
| Content Type | Text |
| Resource Type | Article |
