An approximately fast algorithm for deciding the validity of disjunctive normal forms (DNFs) (Q1801736)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: An approximately fast algorithm for deciding the validity of disjunctive normal forms (DNFs) |
scientific article; zbMATH DE number 205788
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | An approximately fast algorithm for deciding the validity of disjunctive normal forms (DNFs) |
scientific article; zbMATH DE number 205788 |
Statements
An approximately fast algorithm for deciding the validity of disjunctive normal forms (DNFs) (English)
0 references
1992
0 references
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.
0 references
disjunctive normal form validity
0 references
NP-complete problem
0 references
