5
$\begingroup$

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?

$\endgroup$
  • 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