this is a new/advanced paper on OR and AND compression of SAT formulas, a newer area of research that seems not covered in any textbooks so far.

A simple proof that AND-compression of NP-complete problems is hard (Dell)

can follow it generally, but not in detail. so:

how would this theory be described to undergraduates if possible?

looking for sketches, overview and/or some examples and intuition on this line of research from expert(s) of the kind that might appear in an undergrad textbook. also does it have any implication on P=?NP?


closed as unclear what you're asking by Juho, David Richerby, András Salamon, Nicholas Mancuso, Luke Mathieson Feb 23 '15 at 23:50

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 3
    $\begingroup$ The cited paper Infeasibility of Instance Compression and Succinct PCPs for NP∗ seemed (to me) somewhat more comprehensible. It also discusses applications to cryptography; namely, to the creation of collision-resistant hash functions. $\endgroup$ – Patrick Jun 5 '14 at 13:18
  • $\begingroup$ @Patrick thx here is the link to the paper & note also some further discussion in TCS chat, hope others can join in $\endgroup$ – vzn Jun 12 '14 at 0:42
  • 1
    $\begingroup$ You can follow it in general, but not in detail. What in particular is confusing? What should be clarified? What parts of it are "not suitable for undergrads"? $\endgroup$ – Juho Feb 23 '15 at 10:08