4 ms·

>...and the recent works of Ryan Williams and Ketan Mulmuley, which (in different ways) hint at a duality between impossibility proofs and algorithm This is wa

• j2kun 10y ago
  There is a large, emerging body of research in which one proves the impossibility of solving problem A by finding an algorithm for solving a different problem B. For Mulmuley et al. (it's been a while since I was in the thick of this) it's finding an algorithm for computing a particular decomposition of a representation[1] having to do with determinants and permanents. This essentially shows the matrix permanent formula can't be written as a determinant of a small matrix (of smaller formulas of the variables), which is the "algebraic" analogue of P vs NP, and which Mulmuley et al. believe will pave a road toward P vs NP. Last I heard there was a serious blow to this program. (edit [3]) For Ryan Williams, it's a more direct approach to separating complexity classes such as ACC (a small circuit class) and NEXP (a large turing machine class), where this[2] is the most amazing explanatory technical document I have seen for almost anything. He also has this program whereby if you can find faster algorithms for boolean satisfiability (SAT)—that is, faster exponential-time algorithms—you get complexity class separations "for free." [1]: https://en.wikipedia.org/wiki/Representation_theory https://en.wikipedia.org/wiki/Representation_theory [2]: https://arxiv.org/abs/1111.1261 https://arxiv.org/abs/1111.1261 [3]: https://arxiv.org/abs/1604.06431 https://arxiv.org/abs/1604.06431
  • deleted 10y ago
    [deleted]