Non-Uniform Hardness for NP via Black-Box Adversaries

Albert Atserias

Published in: Electron. Colloquium Comput. Complex. (2005)

Keyphrases

black box
computational complexity
np complete
np hard
phase transition
black boxes
white box
rule extraction
test cases
integration testing
state transition
white box testing
learning theory
lower bound
hybrid systems
agnostic learning
worst case
training data
decision trees