tag:blogger.com,1999:blog-3722233.post6203970001887820031..comments2024-11-14T17:42:16.782-06:00Comments on Computational Complexity: The Base of Computational ComplexityLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger21125tag:blogger.com,1999:blog-3722233.post-37160017059366619092010-07-07T19:48:03.106-05:002010-07-07T19:48:03.106-05:00NP+complete-problem
navigation, search
In computat...NP+complete-problem<br />navigation, search<br />In computational complexity theory, the complexity class NP-complete (abbreviated NP-C or NPC), is a class of problems having two properties:<br /> * It is in the set of NP (nondeterministic polynomial time) problems: Any given solution to the problem can be verified quickly (in polynomial time).<br /> * It is also in the set of NP-hard problems: All NP problems were converted into this single transformation of the inputs in polynomial time. The given solution the problem is verified quickly, there is found efficient isys to locate solutions in the first place; indeed, the most notable characteristic of NP-complete problems is the fast solutions compound quickly. The time required to solve the problem using an algorithm increases very quickly as the size of the problem grows. As a result, the time required to solve even moderately large versions of many of these problems easily reaches into the billions or trillions of years, using any amount of computing power available today. As a consequence, determining whether or it is possible to solve these problems quickly is found as one of the principal unsolved problems in computer science. Now it is solved by a method for computing the solutions to NP+complete problems using a reasonable amount of time remaining time is now discovered: computer scientists and programmers still frequently encounter NP-complete problems. An expert programmer is able to recognize an NP-complete problem so he knowingly spent time trying to solve a problem eluding generations of computer scientists. Instead, NP+complete problems are often addressed by using precision algorithms.<br />Contextual Properties of NP+complete problems and solutions:<br />Formal overview<br />NP-complete is a subset of NP, the set of all decision problems whose solutions can be verified in polynomial time; NP may be equivalently defined as the set of decision problems solved in polynomial time on a machine. A problem p in NP is also in NPC if and only if every other problem in NP is transformed into p in polynomial time. NP-complete is be used as an adjective: problems in the class NP-complete were as NP+complete problems.<br />NP-complete problems are studied because the ability to quickly verify solutions to a problem (NP) seems to correlate with the ability to quickly solve problem (P). It is found every problem in NP is quickly solved—as called the P = NP: problem set. The single problem in NP-complete is solved quickly, faster than every problem in NP also quickly solved, because the definition of an NP-complete problem states every problem in NP must be quickly reducible to every problem in NP-complete (it is reduced in polynomial time).M-Wavehttps://www.blogger.com/profile/13408947017986840811noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-29358488806506528052010-05-17T15:55:42.250-05:002010-05-17T15:55:42.250-05:00.m] > .meami.org so domain example.m is created....m] > .meami.org so domain example.m is created if there exists the configuration: http://www.meami.org/example.m there also exists a domain name accessible by the URL http://example.m or http://www.example.m/ Please verify this is set up correctly and fix any mistakes along with prepare a name for any new *.m domain_[*.m] names create{d}.ThankYou.]<br /> http://www.meami.org/search.php meami.org .\>http://www.meami.org/search.php www.meami.org/search.php http://www.meami.org/search.php \.search.php | php = \\ .htm //.html ://meami.org \\ // .\ if (!defined('Mi-.Meami -.o0rg')) exit();}<br />$RecipeInfo['mainormal:in:e// me/ a/. /mi \.org=np. http://www.meami.org/search.php \.search.php | php = \\ .htm //.html ://meami.org \\ // .\']['Version'] = '2010-05-31';<br />$FmtPV['$mainormal:in:e// me/ a/. /mi \.org=np. http://www.meami.org/search.php \.search.php | php = \\ .htm //.html ://meami.org \\ // .\version'] = "'May 31, 2010'";<br />#####################################################################################################################################################################################################################################################################################################################################<br />## DESCRIPTION: The mainormal:in:e// me/ a/. /mi \.org=np. http://www.meami.org/search.php \.search.php | php = \\ .htm //.html ://meami.org \\ // .\ recipe extends FORMED capability on Mi-.Meami -.o0rg, by adding a flexible and easily extensible FORMED processing engine. For info, see http://www.meami.org/search.php ###<br />#####################################################################################################################################################################################################################################################################################################################################<br /><:=\code=:\> e x t e n s i b l e <=:/code/:=><br /><br />www.Mi-.Meami -.o0rg.org/meami/Rooktook/mainormal:in:e// me/ a/. /mi \.org=np. http://www.meami.org/search.php \.search.php | php = \\ .htm //.html ://meami.org \\ // .\, or the mainormal:in:e// me/ a/. /mi \.org=np.visits http://www.meami.org/search.php \.search.php | php = \\ .htm //.html ://meami.org \\ // .\ site at /WWW /.mainormal:in:e// me/ a/. /mi \.org=np /. http://www.meami.org/search.php \.search.php | php = \\ .htm //.html ://meami.org \\ // .\ /MEAMI.ORG. Author: M. Musatov, Copyright 2010.M-Wavehttps://www.blogger.com/profile/13408947017986840811noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-42453607170650422922010-05-04T06:16:00.585-05:002010-05-04T06:16:00.585-05:00Measuring complexity using the problem size is a s...Measuring complexity using the problem size is a shorthand, not something fundamental to the field. Parameterized complexity already has shown how in certain instances this can be too simplistic.Alex Lopez-Ortiznoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-87334584500803465502010-05-02T22:00:49.857-05:002010-05-02T22:00:49.857-05:00Well, I'll be sorry to see this thread disappe...Well, I'll be sorry to see this thread disappear! Lance asked a great question in "What is the base of computational complexity?" ... <br /><br />Further reflection suggests (to me) that category theory has a pretty good answer ready-to-hand: "The base of complexity theory is a <i>natural</i> pullback to computation, followed by a <i>compatible</i> pushforward to applications."<br /><br />The base ideas of naturality and compatibility (perhaps) have a reasonably well-posed meaning in the context of category theory. <br /><br />But ... uhhh ... please don't ask me Cadet Nog's question just yet "What does that <i>mean</i>, exactly?" <br /><br />Thank you, Lance, for a wonderfully thought-provoking post!John Sidleshttp://www.mrfm.orgnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-85539005443832122462010-05-02T17:14:48.515-05:002010-05-02T17:14:48.515-05:00For those interested in a scientific, principles-b...For those interested in a scientific, principles-based formulation of the foundations of computing, we have taken a step in that direction with the Great Principles of Computing project. See http://greatprinciples.org .Peter Denninghttp://cs.gmu.edu/cne/denningnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-17613893569652347392010-05-02T00:55:32.433-05:002010-05-02T00:55:32.433-05:00Well, real analysis doesn't have a basic set o...Well, real analysis doesn't have a basic set of equations, but if you had to summarize the subject up in one phrase, it would be "convergence".<br /><br />I think I agree with the other Anonymous---there are branches of computer science, each of which has a focus and set of foundational principles, but they don't necessarily look much like each other.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-4254462702644080882010-05-01T16:53:55.747-05:002010-05-01T16:53:55.747-05:00Gilbert said: "The idea that the "base&q...Gilbert said: <i>"The idea that the "base" of physics is F=ma seems misguided to me."</i> <br /><br />You are right ... this precise point is discussed in Mac Lane's book <i>Mathematics: Form and Function</i>, in a chapter titled "Mechanics: Tricks versus Ideas".<br /><br />Mac Lane famously asserts "It has taken me over fifty years to understand the derivation of Hamilton's equations [...] the point of this cautionary tale is the difficulty in getting to the bottom of it all."<br /><br />If we take these ideas of Mac Lane seriously, we see that Lance is asking—in the same spirit as Mac Lane—the question "When we 'get to the bottom' of complexity theory, what key ideas do we find?" <br /><br />This in turn leads us to ask whether (perhaps) the same answer might serve both Lance and Mac Lane ... and since Mac Lane has priority ... we can ask whether Mac Lane's answer can be adapted to serve Lance just as well.<br /><br />Mac Lane famously wrote "I did not invent category theory to talk about functors. I invented it to talk about natural transformations." <br /><br />So if we embrace the Mac Lane hypothesis: <i> Computational complexity is all about natural transformations</i> then we have answered Lance's question ... or at the very least, we have transformed it naturally! :)<br /><br />From the resulting Mac Lane-esque point-of-view, algorithms do not solve problems, but rather, represent natural transformations of problems into forms in which (perhaps) the problem itself is more readily understood, or salient aspects of the problem are more readily computed.<br /><br />From this Mac Lane point-of-view, proofs and simulations are simply natural pullbacks from premises to theses, followed by natural pushforwards to further theses and to practical applications. Turing Machines, for example, are a general class of particularly hard-to-pullback dynamical processes, whose dynamics is governed by particularly simple Boolean algebras on particularly low-dimension finite-field state-spaces.<br /><br />How useful is this naturality-driven view of computational complexity (and its close cousin, simulation theory)? Well, my wife and I are fond of a hilarious Star Trek episode in which teenager Jake attempts to explain the Federation's no-money economic system to Nog, the mercantile Ferengi.<br /><br /><b>Jake:</b> "We work to better ourselves and the rest of humanity."<br /><br /><b>Nog:</b> What does that <i>mean</i> exactly?"<br /><br />The point being, we are still in the processes of discovering how far these Mac Lane-style ways of thinking can be pushed.<br /><br />Of course, there are *many* other good ways of thinking about computational complexity ... and it is *not* desirable that everyone think alike ... because healthy ecosystems are diverse ecosystems.John Sidleshttp://www.mrfm.orgnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-66906017986958254692010-05-01T12:38:55.349-05:002010-05-01T12:38:55.349-05:00The idea that the "base" of physics is F...The idea that the "base" of physics is F=ma seems misguided to me. What about experimentation? Reducing natural sciences to their models seems to eschew their essence. Starting from F=ma, and some basic axioms, you could derive many interesting mathematical consequences. However, to me, the genius and heart of physics is that you could try to test gravity, go slide a block down a ramp and discover friction. You might ponder and communicate your results using equations, but the basis is experimentation.Gilberthttps://www.blogger.com/profile/12848246894741812189noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-78917539849356069972010-05-01T12:07:16.896-05:002010-05-01T12:07:16.896-05:00There are several equations in Mathematical Biolog...There are several equations in Mathematical Biology which are sometimes claimed to be the equivalent of e^(pi i) = -1, or F = mA. To nitpick three of the best known. <br /><br />(a) Hardy-Weinberg equilibrium [yes, that Hardy] has a dozen assumptions built in, which are not biologically plausible. Hence there are epicycles built on it, which take a semester to go through.<br /><br />(b) Hodkins-Huxley requires eyeballing graphs of voltage-clamp measurements and determining what part of the graph corresponds to what part of the model. A conference that I went to a few years ago had a paper on an artificial intelligence program that would do this grad student work, essentially lining up the<br />epicycles. I don't accept that nerves and brains work according the the paradigm.<br /><br />(c) Michaelis-Menten kinetics assume many things, most specifically that all behavior is continuous, whereas we know that individual molecules of enzyme do nothing catalytic, and then randomly a molecule of substrate bumps into the enzyme by diffusion, they connect, the<br />catalysis is done, the product molecule(s) diffuse away, in a discrete way.JonVosPosthttps://www.blogger.com/profile/11782744243454673221noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-34522388707258908892010-04-30T19:07:46.186-05:002010-04-30T19:07:46.186-05:00Newton's law of computation thread at http://l...Newton's law of computation thread at http://lists.ccs.neu.edu/pipermail/prl/2007q1/thread.html#1674 is goodAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-4163931837419599022010-04-30T18:09:34.366-05:002010-04-30T18:09:34.366-05:00I find it interesting that there have been two err...I find it interesting that there have been two errors noted politely in the comments. Had BILL been the author of this entry, I suspect the comments would have been in the form of attacks.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-26117640652399276872010-04-30T14:05:40.999-05:002010-04-30T14:05:40.999-05:00To algebraic geometers, the base of computational ...To algebraic geometers, the base of computational complexity is both simple: <i>pullback</i> to a computation; <i>pushforward</i> to an application. <br /><br />Of course, to algebraic geometers <i>all</i> of mathematics is the study of natural pullbacks and pushforwards. :)<br /><br />The engineering community too works increasingly with this toolset ... because this style of mathematical reasoning is natural to systems engineering too.John Sidleshttp://www.mrfm.orgnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-49245945237613359932010-04-30T12:55:59.728-05:002010-04-30T12:55:59.728-05:00I was really excited to see "The Data-Structu...I was really excited to see "The Data-Structure Canon" on the cover of CACM. Hey cool! Someone finally arguing that we need to update the basic vocabulary of data structures taught to undergrads and computing professionals after 30 years of stagnation. (Bloom filters? van Emde Boas trees? Multilevel search trees? Fractional cascading? Treaps? Atomic heaps? Cuckoo hashing? Making data structures dynamic/parametric/kinetic/persistent/functional/history-independent/external-memory/cache-oblivious/succinct? Cell probe lower bounds? Communication complexity? Hash tables that use anything less obviously stupid than singly linked lists for chaining?)<br /><br />I should have known better.JeffEhttps://www.blogger.com/profile/17633745186684887140noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-8329700476242926192010-04-30T10:59:34.437-05:002010-04-30T10:59:34.437-05:00Updated. Not my day today.Updated. Not my day today.Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-18422877588124691812010-04-30T10:05:05.960-05:002010-04-30T10:05:05.960-05:00Typo 2: “What we theorists can differ considerably...Typo 2: “What we theorists can differ considerably from AI and operating systems?” Huh?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-83408337324259863392010-04-30T08:22:43.265-05:002010-04-30T08:22:43.265-05:00Well, "defining" and "finding a bas...Well, "defining" and "finding a base of" are two different things, but when I try to give someone the idea of complexity theory, I usually say "This is the study of the optimal use of space and time when solving a problem, for a certain value of `optimal'."<br /><br />I don't think there is a list of equations from which one could derive complexity theory naturally. Physics and chem are theories in the logical sense (i.e., a set of axioms), and as such, I see complexity theory as an axiom-less system -- except maybe Church-Turing thesis.Michanoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-42598706735186802542010-04-30T08:18:16.826-05:002010-04-30T08:18:16.826-05:00Lambda calculus. Functional techniques help compu...Lambda calculus. Functional techniques help computers help us reason about programs so we can verify algorithms are correct. They also help us reduce computation to its essentials.Geoff Knauthhttps://www.blogger.com/profile/12025560607512616605noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-65364364202719559072010-04-30T08:10:32.716-05:002010-04-30T08:10:32.716-05:00Why is there a problem of focus? There are just di...Why is there a problem of focus? There are just different branches that focus on different things. Its not a problem, but an aspect of diversity.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-60042647510992622312010-04-30T07:41:45.252-05:002010-04-30T07:41:45.252-05:00Anon 1: Thanks and fixed.Anon 1: Thanks and fixed.Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-10128435256683506622010-04-30T07:37:42.685-05:002010-04-30T07:37:42.685-05:00This confusion arises because people mistakenly be...This confusion arises because people mistakenly believe complexity theory to be a science like physics or biology. It isn't. It is a field of mathematics, and should be compared with real analysis or differential geometry. What are the basic equations of real analysis? If one believes that real analysis is baseless, then so is complexity theory. If one believes real analysis has some basic equations, then we can come up with similar basic equations for complexity theory too.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-89454734709530385402010-04-30T07:35:03.618-05:002010-04-30T07:35:03.618-05:00typo: "...data structures as one of the found...typo: "...data structures as one of the foundations of *computer science."Anonymousnoreply@blogger.com