tag:blogger.com,1999:blog-3722233.post7475523893806375286..comments2024-07-16T20:11:35.823-05:00Comments on Computational Complexity: I tell my class that P is important because... but is that really true?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger19125tag:blogger.com,1999:blog-3722233.post-44932022927126566742021-03-09T00:38:37.528-06:002021-03-09T00:38:37.528-06:00As an actual software developer, what we ACTUALLY ...As an actual software developer, what we ACTUALLY need to provide the world the benefits of the "P=NP utopia" is NOT a specific resolution to P vs. NP.<br /><br />No, it is really this: An explicit algorithm for 3-SAT (or another NP-hard problem) that is DOMINATED by an n^k polynomial with k < O(10) for all n < O(2^1000). Basically, an algorithm that is effectively a low-degree polynomial for almost any data set we'd actually feed it. A sufficiently slow-growing, sub-exponential algorithm is just as good as a literal polynomial time one (maybe even better). <br /><br />So, our responses to the various P vs. NP outcomes would be something like this:<br />1) P=NP, Explicit useful algorithm (e.g. scaling like n^5).<br />The dream scenario. YES, we'd all jump on this and try to implement it. There'd be a new version of the internet by the time we finished. <br /><br />2) P=NP, Explicit but unusable algorithm (e.g. n^50, n^10K)<br />The hunt is on! Improve the constants and exponent to get a usable algorithm, or prove we can't beat the bad one. Basically P vs. NP all over again. <br /><br />3) P=NP, but non-constructive:<br />Get back to us when you've got some idea what the algorithm might look like. <br /><br />3) P!=NP, non-constructive:<br />Well that blows, but deep down we're not really surprised. How bad is it? Is brute force really the best we can do with 3-SAT, or can we still hope for "effectively" P=NP on non-enormous 'n' inputs?<br /><br />4) P!=NP, brute force is the best you can do (e.g. "Strong Exponential Time Hypothesis" (SETH))<br />Well, at least we won't waste any more time dreaming of improvement. Let's see if it holds for quantum machines...<br /><br />5) P!=NP, but far better algorithms than any we know of for 3-SAT must exist.<br />Okay, then basically case (2) depending on what the floor is. <br /><br />4) P!=NP, which we proved by showing you can do 3-SAT in something like 2^log(log(n)) but no better:<br />Oh really? So basically we CAN solve NP-hard problem instance for any sane value of n in effectively polynomial time. We'll treat this as a variant of case (1). zyezeknoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-31467143426612266152018-07-06T16:55:24.727-05:002018-07-06T16:55:24.727-05:00It was updated in
https://zenodo.org/record/13069...It was updated in<br /><br />https://zenodo.org/record/1306970Frank Vegahttps://www.blogger.com/profile/15257641208909866601noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-19050732265701641312018-07-06T16:39:28.642-05:002018-07-06T16:39:28.642-05:00Given an instance of $\textit{XOR 2SAT}$ and a pos...Given an instance of $\textit{XOR 2SAT}$ and a positive integer $2^{K}$, the problem exponential exclusive-or 2-satisfiability consists in deciding whether this Boolean formula has a truth assignment with at leat $K$ satisfiable clauses. We prove exponential exclusive-or 2-satisfiability is in $QP$ and $\textit{NP-complete}$. In this way, we show $QP \subseteq NP$.<br /><br />https://zenodo.org/record/1306965<br /><br />https://www.academia.edu/36993851/QP_versus_NPFrank Vegahttps://www.blogger.com/profile/15257641208909866601noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-22868353741262664792018-06-26T09:52:45.421-05:002018-06-26T09:52:45.421-05:00P versus NP is considered as one of the most impor...P versus NP is considered as one of the most important open problems in computer science. This consists in knowing the answer of the following question: Is P equal to NP? This question was first mentioned in a letter written by John Nash to the National Security Agency in 1955. A precise statement of the P versus NP problem was introduced independently in 1971 by Stephen Cook and Leonid Levin. Since that date, all efforts to find a proof for this problem have failed. Another major complexity classes are LOGSPACE and NLOGSPACE. Whether LOGSPACE = NLOGSPACE is another fundamental question that it is as important as it is unresolved. SAT is easier if the number of literals in a clause is limited to at most 2, in which case the problem is called 2SAT. This problem can be solved in polynomial time, and in fact is complete for the complexity class NLOGSPACE. If additionally all OR operations in literals are changed to XOR operations, the result is called exclusive-or 2-satisfiability, which is a problem complete for the complexity class LOGSPACE. Given an instance of exclusive-or 2-satisfiability and a positive integer K, the problem maximum exclusive-or 2-satisfiability consists in deciding whether this Boolean formula has a truth assignment with at leat K satisfiable clauses. We prove that maximum exclusive-or 2-satisfiability is in NLOGSPACE. Moreover, we demonstrate this problem is NP-complete. To attack the P versus NP question the concept of NP-completeness has been very useful. If any single NP-complete problem can be solved in polynomial time, then every NP problem has a polynomial time algorithm. Since every language in the class NLOGSPACE is in P, then we show that our problem is in P and NP-complete and thus, P = NP.<br /><br />https://zenodo.org/record/1297654<br /><br />https://www.academia.edu/36915996/P_versus_NPFrank Vegahttps://www.blogger.com/profile/15257641208909866601noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-11313532235918436852018-06-23T01:14:22.699-05:002018-06-23T01:14:22.699-05:00Worst-case might be overemphasized in research, bu...Worst-case might be overemphasized in research, but that's for three very good reasons:<br />1. Worst-case gives firm reliability guarantees;<br />2. Average-case analysis is considerably more difficult and mathematically intensive than worst-case, generally relegated to graduate study. See e.g. https://lucatrevisan.wordpress.com/2017/09/08/beyond-worst-case-analysis-lecture-2/<br />3. "Best-case" analysis is basically trash. There is nothing "prudent" or "fruitful" about observing that some trivial family of instances causes your algorithm to abort early. If you were to buff up your model of best-case analysis to be more resistant to derailing by trivial instances, you'd end up with something at the level of mathematical sophistication of average-case analysis, which, again, is too difficult a toolset for widespread usage.Greghttps://www.blogger.com/profile/03676035237635094814noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-12843252693421369982018-06-12T05:48:26.798-05:002018-06-12T05:48:26.798-05:00Great News.
IF, P = NP
In the factorization of e...Great News.<br /><br />IF, P = NP<br /><br />In the factorization of every odd number.<br /><br />published in: International Journal of Engineering and Future Technology Vol 16 (1) 2019.<br /><br />Is online now.Anonymoushttps://www.blogger.com/profile/10979851540109030630noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-59129488473613930492018-06-08T18:58:51.138-05:002018-06-08T18:58:51.138-05:00I think that your point 2) somewhat corresponds to...I think that your point 2) somewhat corresponds to what Scott Aaronson described as "8. The Self-Referential Argument" in his "Reasons to believe" post:<br /><a href="https://www.scottaaronson.com/blog/?p=122" rel="nofollow"><br />https://www.scottaaronson.com/blog/?p=122</a><br /><br />(Presumably that's also similar to what Lance wrote in _The Golden Ticket_, but I haven't read that).<br /><br />This only stuck in my memory because a while ago, I commented on a "Godel's Lost Letter" blog entry describing "A Panel on P vs. NP":<br /><a href="https://rjlipton.wordpress.com/2017/02/05/a-panel-on-p-vs-np/#comment-80215" rel="nofollow"><br />https://rjlipton.wordpress.com/2017/02/05/a-panel-on-p-vs-np/#comment-80215</a><br /><br />Basically, I was saying that even if P!=NP, you could still possibly figure out what the smallest circuit for SAT is (for _tiny_ problems), using a SAT solver. Then, incorporate that circuit into the solver; if it's actually an improvement, then you can find the best circuit for a _slightly_ larger problem...<br /><br />Since my guess is that P!=NP, I don't think this would get very far (and would be a lot of work, and use a ton of CPUs). And if the circuit size for SAT increases quickly for small problems, that would only be circumstantial evidence that P!=NP. (However, it would find an optimal SAT-solving circuit for small problems, as a side effect. Admittedly, probably only very small problems.../)<br />Josh Burdickhttps://www.blogger.com/profile/12231348292069164630noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-49627816150417451432018-06-08T09:34:51.023-05:002018-06-08T09:34:51.023-05:00Hold on your holy crowd. What if the proof that P=...Hold on your holy crowd. What if the proof that P=NP<br />is non-constructive after all ? It would shed little, to none light on things.<br /><br />(Incidentally, what is so wrong about saying NP=P ? Come on guys it is an equality after all and not an assignment.) <br /> The glorious, The Almighty, His Excellencyhttp://www.thereisnone.comnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-51929910149479508582018-06-08T07:14:25.849-05:002018-06-08T07:14:25.849-05:00I think the relative lack of polytime algorithms w...I think the relative lack of polytime algorithms with a large exponent is simply due to the fact that coming with a say O(n^17) algorithm is very hard: The algorithm has to be complicated for its complexity to be O(n^17), at least if the value 17 does not appear explicitly in the input ("finding cliques of size 17"). On the other hand, coming with an algorithm in O(2^n) is often quite simpler. Our limited brains are still able to understand four nested loops, or maybe 5 or 6 for the brightest amongst us, but are short of understanding the power of tens of nested loops. Of course, this statement has no proof nor evidence, but I am nevertheless convinced that there is some truth in it.B.noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-42776410894116054262018-06-07T23:25:12.783-05:002018-06-07T23:25:12.783-05:00" If Lance proves P=NP next week then the con..." If Lance proves P=NP next week then the consequences are enormous for real people working on real computing problems."<br /><br />I am not sure that is true either. A proof of that might not have any impact for at least quite some time. It is not as if people just close their shop once they know that the problem is NP-hard. People have developed efficient solvers for hard problems, and it is very hard to believe any of these algorithms will be displaced anytime soon.Ravihttps://www.blogger.com/profile/03453457907385341473noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-8991034841007607932018-06-07T23:09:00.738-05:002018-06-07T23:09:00.738-05:00P=NP
http://vixra.org/abs/1805.0399P=NP<br /><br />http://vixra.org/abs/1805.0399Yuly Shipilevskyhttps://www.blogger.com/profile/13699450530150796472noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-18581495523199234132018-06-07T12:38:40.371-05:002018-06-07T12:38:40.371-05:00Determining whether a graph has a clique of size 1...Determining whether a graph has a clique of size 100 takes O(n^100) time using exhaustive search. Does that constitute a "natural problem"?Sebastian Oberhoffnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-87574286557146994072018-06-07T10:28:15.431-05:002018-06-07T10:28:15.431-05:00SAT cannot still be used to mine bitcoin efficient...SAT cannot still be used to mine bitcoin efficiently (and it is a very practical problem!).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-45388634992025824972018-06-07T09:16:58.386-05:002018-06-07T09:16:58.386-05:00On (4): I do applied operations research at Google...On (4): I do applied operations research at Google. We solve mixed integer linear programs w/ ~millions of constraints and variables every hour or so, often achieving optimality because practical solvers are very good. When we set it up wrong (bad conditioning, scaling, etc.) it takes 8-12 hours to finish. When we set it up right, 15 minutes to 2 hours.<br /><br />Rather than what you said in (4), I'd say "If your problem is NP hard, then there are great tools but you have to work a lot harder (and know a lot more theory) to make sure you don't spiral out of control in terms of time/space." If we mess up the set up for the problem (we as in our group collectively, not all of whom are experts in OR), we have to go ask the OR experts for help to figure out what, in theory, is causing our problem to solve slowly. Also, my impression is that a constant factor approximation would not fly for most applications, and it's FPTAS or use a solver (for serious problems), or give up on theory and use randomized greedy until it becomes a problem.<br /><br />That being said, a colleague of mine came to me with what turned out to be the dynamic transitive closure problem for DAGs, and I was delighted to learn (via some notes of Virginia Williams) that there's a polynomial lower bound depending on the matrix multiplication exponent. This informed me and my colleague that she couldn't expect to have a data structure for this problem with a log-time update. That episode makes me think fine-grained complexity makes P more relevant, if not in its relation to NP, then among the relation between problems in P.j2kunhttps://www.blogger.com/profile/08041921049916424212noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-67125087555140515702018-06-07T07:07:15.168-05:002018-06-07T07:07:15.168-05:00Even if SAT is not in P there may be some few effi...Even if SAT is not in P there may be some few efficient SAT-solvers that handle all real world problems. See Knuth's fascicle "Satisfiability" for an overview of the huge progress that has already been achieved. Though I am not subscribing to his thesis that P=NP (but non-constructively!) I think it possible that SAT can be solved, though not necessarily in general, but for most, if not all, practical purposes. Also, even if NP is not contained in P/poly there may be sufficiently efficient circuits for all practical purposes.<br />Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-44263309623973600652018-06-07T05:46:15.104-05:002018-06-07T05:46:15.104-05:00I do work in "the real world", and I do ...I do work in "the real world", and I do say things like 4).<br /><br />Although often, the people I discuss with when something like that comes up have no idea what NP-complete problems are, so that typically gets translated to "We don't have the resources to give an exact solution", or something similar.<br /><br />As for 5), I'm on Your Darlings side. A proof may give great insight, and it may have a real effect on real computing problems. But that remains to be seen. Abigailhttps://www.blogger.com/profile/14202894297731782841noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-49565369493784759292018-06-07T01:00:01.003-05:002018-06-07T01:00:01.003-05:00One example coming to mind is the approximation al...One example coming to mind is the approximation algorithm for non-negative permanents (Jerrum, Sinclair, and Vigoda). Despite some effort to optimise its running time, the current best is still roughly n^7. It doesn't seem to be an easy problem to solve in practise either.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-38086849792244044972018-06-06T20:54:00.797-05:002018-06-06T20:54:00.797-05:00On 1, overwhelming focus on worst case time comple...On 1, overwhelming focus on worst case time complexity on all problems took us in the wrong path.<br /><br /> Prudent one would have been to study worst case time complexity for P and best case time complexity for NP problems and that would have brought us more fruitfulness.<br /><br />On 2, everything is hard/impossible when we don't know about it. Once we know about it, then it is a question of possible or not.<br />Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-2313886215811808822018-06-06T20:04:38.223-05:002018-06-06T20:04:38.223-05:00In the real world people are faced with NP-complet...In the real world people are faced with NP-complete problems. I think they tend to solve them using heuristics rather than approximation algorithms with rigorous guarantees. SAT solvers are a good example of this: they seem to work well on "most" real-world instances.Anonymousnoreply@blogger.com