Finite Model Theory and Proof Complexity Revisited: Distinguishing Graphs in Choiceless Polynomial Time and the Extended Polynomial Calculus.
Benedikt PagoPublished in: CSL (2023)
Keyphrases
- polynomial hierarchy
- polynomial time complexity
- worst case
- bounded treewidth
- computational complexity
- polynomial size
- finite model theory
- np complete
- special case
- fixed parameter tractable
- theorem prover
- database
- dnf formulas
- natural deduction
- theorem proving
- conp complete
- database theory
- conjunctive queries
- distributed databases
- data types
- databases