On the Hardness of Satisfiability with Bounded Occurrences in the Polynomial-Time Hierarchy.
Ishay HavivOded RegevAmnon Ta-ShmaPublished in: Theory Comput. (2007)
Keyphrases
- np complete
- computational complexity
- bounded treewidth
- fixed parameter tractable
- phase transition
- satisfiability problem
- np hardness
- worst case
- np hard
- special case
- acyclic conjunctive queries
- sat problem
- pattern matching
- polynomial size
- randomly generated
- truth table
- random instances
- propositional logic
- decision problems
- approximation algorithms
- conjunctive queries
- lower level
- data complexity
- computational problems
- hierarchical structure
- first order logic
- stochastic local search
- knowledge base
- abstract argumentation
- cnf formula
- computational properties
- learning theory