tag:blogger.com,1999:blog-3722233.post1397026803785026590..comments2024-05-20T10:34:03.365-05:00Comments on Computational Complexity: Fifty Years of P vs. NP and the Possibility of the ImpossibleLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger6125tag:blogger.com,1999:blog-3722233.post-39278694283282953422021-12-20T05:18:45.959-06:002021-12-20T05:18:45.959-06:00An obvious feature is that factoring formuals are ...An obvious feature is that factoring formuals are similar to unique sat, i.e. the number of solutions is very small.<br /><br />Perhaps there is also a conjecture (by Impagliazzo?) which says that SAT formulas with many satisfying assignments are easier. <br /><br />But I think that the number of solutions is not enough; also a sort of "self-reference degree" plays an important role: e.g. a flip on every variable (or on most variables) can propagate to the whole formula. <br /><br />I have in mind SAT formulas from Ramsey problems (e.g. the k-colorable rectangle-free grid problem); the SAT formulas are very small (and you can further restrict the solution space adding a simple order on the "elements" of the solution) but completely out of reach of current computational power.<br />Marzio De Biasihttps://www.blogger.com/profile/18441670787376943932noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-62085197490178532542021-12-18T09:48:00.656-06:002021-12-18T09:48:00.656-06:00Is it know WHY the formulas coming out of AES and ...Is it know WHY the formulas coming out of AES and factoring and whatnot are hard? Is there a clean statement like:<br /><br />If the clauses overlap X amount then the SAT is hardgasarchhttps://www.blogger.com/profile/03004932739846901628noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-77128464147975921632021-12-18T04:55:08.091-06:002021-12-18T04:55:08.091-06:00Most formulas in the SAT competition have millions...Most formulas in the SAT competition have millions of variables, but it seems that there are formulas with <100k variables that correspond to intractable factoring instances: https://arxiv.org/abs/cs/9809117. So I guess it is because of the type of the formula.<br /><br />In this twitter thread https://twitter.com/soosmate/status/1374818799149518852 a SAT solver expert makes the case that the size of a CNF has nothing to do with its hardness by giving a CNF with <10k variables whose solving amounts to breaking 128 bit AES.Tuukka Korhonennoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-43979981013012388872021-12-17T16:07:19.479-06:002021-12-17T16:07:19.479-06:00If we took two large primes, multiplied them, and ...If we took two large primes, multiplied them, and made the <br />factoring problem into a SAT problem I assume that that SAT problem would be hard. But is this because<br />1) Its a large formula, or<br />2) the TYPE of formula it is.gasarchhttps://www.blogger.com/profile/03004932739846901628noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-59723932051040242512021-12-17T14:50:11.348-06:002021-12-17T14:50:11.348-06:00Factoring is not harder than SAT in practice, it i...Factoring is not harder than SAT in practice, it is just that the SAT instances that we care about are easy while the factoring instances that we care about are hard.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-32920172223789916232021-12-17T14:31:00.813-06:002021-12-17T14:31:00.813-06:00A summary and a question:
Some NPC problems are do...A summary and a question:<br />Some NPC problems are doable via ML or SAT-Solvers or NEWTHING<br />Factoring is still hard.<br /><br />Can ML or SAT-Solvers or NEWTHING be used on factoring?<br />Why is factoring in the HARD part of NP, whereas SAT might be<br />in the EASY part of NP?<br /><br />I am sure we can't prove any of this now, but what is the intuition for Factoring being hard given that other problems are easy. <br />gasarchhttps://www.blogger.com/profile/03004932739846901628noreply@blogger.com