In Arora's paper, he wrote,

Papadimitriou and Yannakakis also noted that the classical style of reduction (Cook-Levin-Karp [41, 99, 85]) relies on representing a computational history by a combinatorial problem. A computational history is a very non-robust object, since even changing a bit in it can affect its correctness. This nonrobustness lay at the root of the difficulty in proving inapproximability results.

What does he mean by this statement? In particular: what does it mean by 'computational history', and 'representing a computational history by a combinatorial problem'?

I conjecture that: [it is] a very non-robust object, he means that computation could make many many errors. So, in the last statement in the paragraph, maybe he means nonrobustness [the ability to make many errors] lay at the root of the difficulty in proving inapproximability.

Could someone tell me how nonrobustness exists in Karp/Levin reduction?

  • 3
    $\begingroup$ I suggest instead of reading this survey to read the relevant chapter in the more recent textbook of Arora and Barak. $\endgroup$ – Yuval Filmus Apr 26 '18 at 13:16

The computational history consists of the contents of the tape of the Turing machine after each step. These are the variables in the SAT instance produced by the Cook-Levin theorem, which is the combinatorial problem which represents the computational history.

This representation is fragile in the sense that even when the SAT instance is unsatisfiable, we may be able to satisfy almost all of its clauses - say, all but a constant number. This is because the reduction in the Cook-Levin theorem is very local: if we flip a single bit in the computational history, then this falsifies only a small number of clauses. In contrast, the PCP theorem guarantees that the SAT instance is either satisfiable or at most 99% of its clauses can be satisfied, and this implies a hardness of approximation result for MAX-SAT.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.