Hardness Amplification in Proof Complexity

Paul Beame Trinh Huynh Toniann Pitassi

Published in: CoRR (2009)

Keyphrases

computational complexity
worst case
np hardness
databases
np hard
decision problems
data structure
search algorithm
data mining
relational databases
information theoretic
theorem prover
theorem proving
high computational complexity
lower complexity