Recognizing Renamable Generalized Propositional Horn Formulas Is NP-complete.
Thomas EiterPekka KilpeläinenHeikki MannilaPublished in: Discret. Appl. Math. (1995)
Keyphrases
- knowledge compilation
- horn formulas
- np complete
- randomly generated
- cnf formula
- prime implicates
- constraint satisfaction problems
- satisfiability problem
- computational complexity
- np hard
- polynomial time complexity
- normal form
- pspace complete
- bounded treewidth
- target language
- polynomial size
- conjunctive queries
- propositional logic
- machine translation
- special case
- expert systems
- objective function