Search Results

« Previous | 2 of 2
« Back to Results List | Edit My Search | New Search | Selected Items
thumbnail image
PDF
PDF-1(139.68 kb)
Citation & Export
View statistics
Staff View
http://rightsstatements.org/vocab/InC/1.0/

Citation & Export
Hide

Simple citation

Gurvich, Vladimir & Khachiyan, Leonid. On Generating the Irredundant Conjunctive And Disjunctive Normal Forms Of Monotone Boolean Functions. Retrieved from https://doi.org/doi:10.7282/T3Z89GWD

Export

Click here for information about Citation Management Tools at Rutgers.

Statistics
Hide

Description

On Generating the Irredundant Conjunctive And Disjunctive Normal Forms Of Monotone Boolean Functions (1995)
Vladimir Gurvich, Leonid Khachiyan
AbstractLet f:{0,1}n→{0,1} be a monotone Boolean function whose value at any point x∈{0,1}n can be determined in time t. Denote by the irredundant CNF of f, where C is the set of the prime implicates of f. Similarly, let be the irredundant DNF of the same function, where D is the set of the prime implicants of f. We show that given subsets C′⊆C and D′⊆D such that (C′,D′)≠(C,D), a new term in (C⧹C′)∪(D⧹D′) can be found in time , where m=|C′|+|D′|. In particular, if f(x) can be evaluated for every x∈{0,1}n in polynomial time, then the forms c and d can be jointly generated in incremental quasi-polynomial time. On the other hand, even for the class of ∧,∨-formulae f of depth 2, i.e., for CNFs or DNFs, it is unlikely that uniform sampling from within the set of the prime implicates and implicants of f can be carried out in time bounded by a quasi-polynomial 2polylog(·) in the input size of f. We also show that for some classes of polynomial-time computable monotone Boolean functions it is NP-hard to test either of the conditions D′=D or C′=C. This provides evidence that for each of these classes neither conjunctive nor disjunctive irredundant normal forms can be generated in total (or incremental) quasi-polynomial time. Such classes of monotone Boolean functions naturally arise in game theory, networks and relay contact circuits, convex programming, and include a subset of ∧,∨-formulae of depth 3.
Persistent URLhttps://doi.org/doi:10.7282/T3Z89GWD
NoteTechnical report LCSR-TR-251
RightsThis Item is protected by copyright and/or related rights.You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use.For other uses you need to obtain permission from the rights-holder(s).