An approximately fast algorithm for deciding the validity of disjunctive normal forms (DNFs)

MaRDI QIDQ1801736zbMATH OpenFDO

Authors Enmin Song, Wenqi Huang

Publication date 1992

Published in Chinese Science Bulletin (Search for Journal in Brave)

zbMATH Keywords

disjunctive normal form validityNP-complete problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Review text

An approximately fast algorithm is given for a model problem --- disjunctive normal form (DNF) validity, which is the dual of an NP- complete problem. By this algorithm, most of the DNF validity problems can be solved in the polynomial time, even though in few cases the time required is longer.

Recommendations

• On deterministic approximation of DNF
• scientific article; zbMATH DE number 4092808
• scientific article; zbMATH DE number 169259
• An algorithm for the satisfiability problem of formulas in conjunctive normal form
• On the learnability of disjunctive normal form formulas

Cited in

(5)

• On deterministic approximation of DNF
• scientific article; zbMATH DE number 4137742 (Why is no real title available?)
• A DNF without Regular Shortest Consensus Path
• scientific article; zbMATH DE number 169259 (Why is no real title available?)
• Checking the satisfiability of formulas represented in disjunctive normal form in the language \(L\). II

This page was built for publication: An approximately fast algorithm for deciding the validity of disjunctive normal forms (DNFs)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1801736)