Computer Science/Discrete Mathematics Seminar I

We say a problem is tractable on average if it can be solved on a "good" fraction of instances by an efficient algorithm. To make this definition precise, we need to make two choices: First, what is a "good" fraction of instances - is it 1%, 51%, 99%, or something else? And second, what should the algorithm do on the instances where it fails to solve the problem? For heuristic algorithms for NP - these are allowed to behave arbitrarily on instances where they fail to solve the problem - it is known that the definition is robust with respect to the fraction of instances. Namely, if all problems in NP can be solved on a 51% fraction of instances by heuristic algorithms, then all problems in NP can be solved on almost all instances by heuristic algorithms. We consider the analogous question for errorless heuristics - these algorithms must output "I don't know" on instances where they fail to solve the problem - and show that if all problems in NP can be solved on even a 1% fraction (in fact even a subconstant fraction) of instances by errorless heuristics, then all problems in NP can be solved on almost all instances by errorless heuristics. (This is based on joint work with Muli Safra)