On the asymptotic Nullstellensatz and Polynomial Calculus proof complexity.
Søren RiisPublished in: Electron. Colloquium Comput. Complex. (2009)
Keyphrases
- worst case
- polynomial hierarchy
- vapnik chervonenkis dimension
- computational complexity
- exponential size
- provably correct
- proof search
- natural deduction
- automated theorem proving
- proof procedure
- space complexity
- linear logic
- database
- theorem prover
- memory requirements
- decision problems
- higher order
- upper bound
- website