tag:blogger.com,1999:blog-3722233.post411297283565155244..comments2024-03-02T02:08:38.816-06:00Comments on Computational Complexity: OptilandLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger11125tag:blogger.com,1999:blog-3722233.post-23039663556618335792021-09-03T15:35:50.859-05:002021-09-03T15:35:50.859-05:00Factoring and similar all-or-nothing-at-all proble...Factoring and similar all-or-nothing-at-all problems are harder than TSP in practice. There is a single factorization, finding any approximate factorization (primal or dual), no matter how close to the correct one, does hot help in any way. Techniques like local search, mathematical programming or ML are powerless in that context.Eduardo Uchoahttps://www.blogger.com/profile/18428305066320507780noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-70398207177443328172020-12-28T10:28:14.879-06:002020-12-28T10:28:14.879-06:00Why assuming P=NP implies that you can find the sm...Why assuming P=NP implies that you can find the smallest solution of a search problem in P time ? I mean, it depends on the size of the solutions to the optimization problem, isn't it?Unknownhttps://www.blogger.com/profile/14289898253944037422noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-54174082378077855552020-12-20T07:31:15.719-06:002020-12-20T07:31:15.719-06:00Thank you. I think this is an important point that...Thank you. I think this is an important point that a lot of newbies (or do people call them noobs nowadays?) are not aware of,yet take P=NP (rather than NP=P) for granted. The historical reason is important, and those of us not having been part of the TCS community will probably be less aware of the preference.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-29380021639658472362020-12-19T23:57:05.702-06:002020-12-19T23:57:05.702-06:00P and NP are names of specific sets, and = here is...P and NP are names of specific sets, and = here is mathematical equality of sets, not variable assignment.<br /><br />Equality of sets is a symmetric relation; P=NP is the same as NP=P. The two statements are the same, but historically we prefer P=NP.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-25746489611055767162020-12-18T00:31:25.495-06:002020-12-18T00:31:25.495-06:00regarding equality notation:
Always had a bit of h...regarding equality notation:<br />Always had a bit of hesitation when thinking of<br />whether it should be P=NP or NP=P. <br />When we assign values to variables, how would you <br />assign to show that NP is literally P, would it <br />not be NP=P ?<br />What's going wrong here ...?<br />Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-30370799684107284012020-12-17T23:22:29.780-06:002020-12-17T23:22:29.780-06:00The "real-life" instances for each probl...The "real-life" instances for each problem differ from problem to problem. As stated above, the "real life" instances of factoring are the hard ones; the "real life" instances of TSP are the (relatively) easy ones.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-21195309726109346182020-12-17T15:28:20.213-06:002020-12-17T15:28:20.213-06:00The whole issue is to make sense of "real-lif...The whole issue is to make sense of "real-life" instances. Are hard factoring problems not real life? Simplex method is not panacea for all instances. The provably poly-time interior point method outperforms Simplex in many large instances. Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-91364090428619455622020-12-17T03:21:17.425-06:002020-12-17T03:21:17.425-06:00I do not understand why it is theoretically imposs...I do not understand why it is theoretically impossible to (a) have an algorithm for NP-complete problems similar to the simplex method for the linear programming, that is, solve all real-life instances fast but being able to artificially construct instances on which the algorithm run exponential time. But at the same time (b) still have cryptography by encoding the messages into exactly the hard instances. Bogdan Grechuknoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-49943397285312476392020-12-16T17:50:07.753-06:002020-12-16T17:50:07.753-06:00AH- good point.
Also, for factoring there really i...AH- good point.<br />Also, for factoring there really is an adversary trying to give you hard cases (prod of two large primes). By contrast I doubt the pubs in England were build for the sole purpose of making TSP for them hard. gasarchhttps://www.blogger.com/profile/03004932739846901628noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-29456648040754181552020-12-16T17:38:19.816-06:002020-12-16T17:38:19.816-06:00For TSP people don't really care about worst-c...For TSP people don't really care about worst-case instances. For Factoring they do.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-33382436503485266272020-12-16T16:57:31.427-06:002020-12-16T16:57:31.427-06:00So for the real world it looks like
Factoring is ...So for the real world it looks like <br />Factoring is harder than TSP.<br />Why is this?<br />One reason: approximating TSP to within BLAH of optimal is worth doing and one may regard the problem as solved; however, for factoring there is no notion of approximate factoring. <br /><br />Any other reason? gasarchhttps://www.blogger.com/profile/03004932739846901628noreply@blogger.com