The Impact of Heterogeneity and Geometry on the Proof Complexity of Random Satisfiability.
Thomas BläsiusTobias FriedrichAndreas GöbelJordi LevyRalf RothenbergerPublished in: CoRR (2020)
Keyphrases
- computational complexity
- decision procedures
- three dimensional
- computational cost
- np complete
- geometry theorem proving
- linear logic
- theorem proving
- space complexity
- conjunctive query containment
- data sets
- random sat
- uniformly distributed
- complexity analysis
- randomly generated
- theorem prover
- phase transition
- decision problems
- worst case