Slashdot Mirror
3D Microfluid Computers Used To Solve NP Problems
Sergio Lucero writes "The Proceedings of the National Academy of Science (PNAS)
just published an
article
on the use of 3D microfluid networks as computers for the
solution of very hard (NP) mathematical problems. So far it looks
like they've solved a specific case of the maximum clique problem,
but of course this also means they can do other stuff."
"First Post" attempts are "Off Topic", not "Trolls". Please read the FAQ and moderating correctly. I say this because Metamod no longer allows us to correct the rampant mislabeling, as it ignores and penalizes us for disagreeing with more than 2 moderations.
"If you can do one, you can do them all"
I believe this applies to the class of NP-complete problems, not NP problems.
Here's the abstract and the first couple of paras of the introduction, for those who can't get access to the article. (I'll get into shit if I set up a mirror.)
Using three-dimensional microfluidic networks for solving computationally hard problems
Daniel T. Chiu, Elena Pezzoli, Hongkai Wu, Abraham D. Stroock, and George M. Whitesides
Abstract
This paper describes the design of a parallel algorithm that uses moving fluids in a three-dimensional microfluidic system to solve a nondeterministically polynomial complete problem (the maximal clique problem) in polynomial time. This algorithm relies on (i) parallel fabrication of the microfluidic system, (ii) parallel searching of all potential solutions by using fluid flow, and (iii) parallel optical readout of all solutions. This algorithm was implemented to solve the maximal clique problem for a simple graph with six vertices. The successful implementation of this algorithm to compute solutions for small-size graphs with fluids in microchannels is not useful, per se, but does suggest broader application for microfluidics in computation and control.
Introduction
Intuitively, a problem is in the class NP (i) if it can be solved only by an algorithm that searches through exponentially many candidate solutions, and (ii) when the correct solution has been identified, verification of the solution can be performed easily (ref. 4). No feasible sequential algorithm is known to solve NP problems. If one can, however, search all candidate solutions simultaneously in parallel, solution of NP problems becomes feasible. The potential for parallel searches is the foundation for interest in DNA-based computation (refs. 5-8) and in part for interest in quantum computation (refs. 9-12). In addition to sequence-specific recognition (the basis of DNA computation) and manipulation and resolution of entangled quantum states (the basis for quantum computation), other physical phenomena or systems might also be suited for solving computational problems. In this paper, we demonstrate the use of moving fluids in a microfluidic system to solve an NP complete problem.
Microfluidic systems are providing the basis for new types of rapid chemical and biological analyses (refs. 1-3). With the increasing complexity of microfluidic systems, there is also a growing need to carry out relatively complex processeslogic operations, fluidic control, and detectionon the chip. Although these processes can be (and usually are) controlled by electronic systems, it would be more natural and compatible to use the same medium (that is, a fluid) to carry out some or all elements of the required computation and control/decision making. Here, we explore the potential of microfluidic systems in computation by using a representative "hard" problem a parallel solution of a nondeterministically polynomial (NP) complete problem [the maximal clique problem (MCP)] for a graph with six vertices. This method we describe uses moving fluids to search the parallel branches of a three-dimensional (3D) microfluidic system simultaneously, exploits parallel fabrication of relief patterns by photolithography, and detects solutions in parallel with fluorescence imaging.Of course exactly the same can be said to those who argue for 'market forces' to run the economy ... personal greed does indeed tend toward local optimizations - but some form of global control and insite can help find global minima (hello Mr Greenspan :-) - anyone who's used logic design tools to do chip design knows in their gut that Mr Friedman was full of it :-)
Local minima my ass. Jesus says not to be greedy, so the United States government should go and beat up anybody that doesn't listen to him. Blow up Iraq, blow up Microsoft. Praise Jesus!
As someone who has lived and breathed this stuff for years and years (and years), I thought I'd chime in and correct the definitions given above, which are better than most that I see, but are still (alas) a bit incorrect. There are so many subtleties to these definitions that it has taken me nearly ten years to feel that I have 'em right. And I still might not.
:-)
Your definition of NP is correct, provided you mention that the verification takes place on a deterministic turing machine, and that verification is done using a polynomial size certificate. If you give me a computational problem X, then I can show you it is in NP by (1) demonstrating that there is a way to express the proper solution x' to an instance x of X using O(f(|x|)) characters, where f(|x|) is a polynomial function, and (2) that given both the instance x and the solution x', you are able to verify using a DTM that x' really is a solution to x in polynomial time.
Your definition of P is correct. You are also correct in saying that P is a subset of NP. Mathematicians are still uncertain whether P is a proper subset of NP -- this is a huge open problem.
Let's tackle your definition of NP-complete next. The correct definition of an NP-complete problem is that it is both a member of NP *and* a member of NP-hard. Note that this does *NOT* mean that NP hard problems cannot be solved in P time. That is a BIG open question, and if you have a proof for it, I'd love to see it.
A problem is defined to be NP-hard if it is polynomial time reducible (on a DTM) to Circut-SAT. This is the very famous Cook-Levin theorem. (The theorem also demonstrates that Circut-SAT happens to be in NP as well, and is hence NP-complete. But that isn't the main point of the theorem -- something people often miss.) Generally when people define the NP-hard set, they say "any problem which is polynomial time reducible to another problem in NP-hard" but of course that is problematic in that it is a circular definition. The genius of the Cook-Levin theorm is that it gave us a base problem for defining the set, and gives us a very illumniating method for looking at the meaning of NP-hard.
Okay. Now that we've got that squared away, I'd like to address two final inaccuracies that I hear a lot. Myth number one: if you can efficiently factorize large integers, you've broken today's best encryption schemes. This is not true. In fact, you must solve the *discrete logarithm* problem in polynomial time in order to break today's encryption schemes. The reason that integer factorization is often substituted here is that usually when you've solved this, you've also solved the discrete logarithm problem. But *not always*. (Witness the L3 algorithm or other lattice reduction algorithms.)
Myth number two: if you have solved integer factorization (or discrete logarithm) then you've proven that P=NP. This is *not* necessarily true. Unfortunately, computer scientists have never been able to classify these problems in the strict P/NP/EXPTIME hierarchy. It is *not* known if either of these problems is NP-complete (or even weaker, simply NP-hard.)
A final variant and twist on both these myths: if you can show that P=NP, then today's modern encryption schemes are failed. This is only partially true. There are some schemes which rely on the computational intractability of NP problems. These schemes would break. However, there are other schemes (such as RSA, and one I just heard about called NTRU) which rely on problems which are *not* understood to be NP-complete (discrete logarithm, and in NTRUs case I think it is change of algebraic rings, which I don't understand so well.) These encryption schemes would *still stand* though most mathematicians would agree that they fall on shakier ground.
Okay, that's my theory lesson for today. I hope everyone has found this useful. If anyone has spotted inaccuracies or blatant lies, please let me know.
love,
the anonymous theory coward
It's far better, imho, to let certain things remain unsolved. NP problems are one class of such things.
If humans solve everything, then we'll grow lazy and ungrateful. Goedel showed that there are infinitely many unsolvable problems in the world (and Turing showed there are infinitely many uncalculable ones), but there's no guarantee that this infinity of problems consists of interesting problems. In fact, they might all be dull ones! And where would that leave us?
Mathematics is where it is today because bygone generations left problems for us to solve. They may have wanted to solve them all, but for whatever reason, they were unable. Are we really better than they? Doesn't conservativism dictate that we should look to our nation's history and traditions when determining what current approach to take?
Where will we be in twenty years if all the interesting mathematical problems are solved? There'll be anarchy in the streets. Unemployed mathematicians and computer scientists will be roaming the nation's highways, raping our women and defiling our basilicas.
I'm not so sure this is a good thing. Certain things man was not meant to know. Certain things are beyond our comprehension by design. If we seek this path, we may bring down divine vengeance upon the National Academy of Sciences and all who are complicit in their proceedings. It is a mark of human hubris, and Xenu won't look favorably upon it.
Friends don't let friends solve NP problems.
How appropriate: Windoze always is pretty nondeterministic. I don't know how it's polynomial, though...
#define X(x,y) x##y
#define X(x,y) x##y
Peter Cordes ; e-mail: X(peter@cordes ,
Not at all.
NP stands for non-deterministic polynomial. Which means that you can solve the problem in polynomial time, but with a non-deterministic machine. Another way to say it is that given a supposed solution to the problem you can test if it is really a solution in polynomial time with a deterministic machine.
By "mirror" you mean pirated copy, right?
Soapwater films do not always settle on the best solution, they often get stuck at a local minimum. The more complex the problem, the more likely they are to find such a local minimum.
-
Stop worrying about the risks of nuclear power and start worrying about the risks of not using nuclear power.
Quite true, also. I was being careful to state the Euclidian nature of the method he was describing, because there are, as you undoubtedly know, other graph problems where it does make quite a difference.
Any sufficiently advanced technology is indistinguishable from a rigged demo
--Andy Finkel (J. Klass?)
The difference between a problem with a straightforward polynomial-time solution and an NP-hard problem is often very small. Be careful!
Any sufficiently advanced technology is indistinguishable from a rigged demo
--Andy Finkel (J. Klass?)
NP-hard: A decidable problem such that any NP problem can be reduced to it in polynomial time.
NP-complete: NP and NP-hard.
There DO exist NP-hard problems which are not NP. In fact, there exists an infinate ascending tower of classes that extend beyond NP (which are all NP-hard problems.)
It looks like they trade off exponential time with exponential space...
... We estimate that the largest graph that might be solved with our algorithm... is 20 vertices. ... If we use space more efficiently ... a 40-vertex graph can be solved in about 20 min."
Excerpts from the conclusion (emphasis mine):
"The strength of this microfluidic system as an analog computational device is its high parallelism. Its weakness is the exponential increase in its physical size with the number of vertices.
Myth number one: if you can efficiently factorize large integers, you've broken today's best encryption schemes. This is not true. In fact, you must solve the *discrete logarithm* problem in polynomial time in order to break today's encryption schemes.
The RSA cryptosystem relies on that factorization is a hard problem. If you find an efficient algorithm to the factorization problem you have broken RSA. RSA may not be the best cryptosystem but it is widely used.
From the RSA Laboratories FAQ 4.0: Question 3.1.3 The most damaging would be for an attacker to discover the private key corresponding to a given public key; this would enable the attacker both to read all messages encrypted with the public key and to forge signatures. The obvious way to do this attack is to factor the public modulus, n, into its two prime factors, p and q. From p, q, and e, the public exponent, the attacker can easily get d, the private exponent. The hard part is factoring n; the security of RSA depends on factoring being difficult.
Well, yeah, but it's not free. You've still got to figure out how to map your specific problem onto some other one that you know how to solve.
Well in theory if you can solve any NP complete problem you can solve them all - you just need to figure out how you can map the new problem onto the solvable one.
Of course there are practical difficulties using these types of analog computer as you scale up, but I don't know how much serious effort has been taken to look for analog approaches that would scale.
I'm not sure if it's a local minimum or not - it was a LONG time ago that I saw this done on TV.
Quantum may well be the practical way to go for NP complete problems, and I believe the general approach is the same as the DNA method you linked to - you figure out how to make your quantum system simultaneously represent all solutions to the problem, then reject the ones you don't want - pretty much the exact opposite of conventional methods.
Well, it better be a damn fast Turing machine if you want to solve any O(N**1000) problems! ;-)
O(X) only applies to stepwise problem solving as done by digital computers (and Turing machines). If you can use an analog/parallel approach, then you have circumvented the complexity entirely.
See the DNA and sphagetti examples in this thread, or my comment about quantum solutions.
It means the problem is parallelizeable.
Not necessarily. You can consider the analog soap bubble computer as a parallel solution, since it is "computing" the solution, but the DNA/quantum computer approaches are radically different... With that paradign you're not relying on the solution method being parallelizeable because you're not trying to derive the solution!.. instead you're assuming that you can create a non-computed set that contains the solution, then remove the non-solutions. If puts the empasis on verification rather than solution generation, and regardless of the problem you can always represent multiple potential solutions in parallel.
No - strong AI is a philosophical problem (for some). There's no reason to believe it's NP complete.
NP complete problems are only hard if you insist on using a digital computer to solve them.
Want to find the shortest set of roads to build to interconnect a bunch of cities? You need a couple of pieces of glass, some round plastic rod and some soapy water...
Cut the rod into 1" lengths, so that you have one per city, then glue them as separators between the two pieces of glass so that the positions of the rods represent the locations of the cities. Dip the completed "computer" into soapy water, and let surace tension and energy minimization do it's job - the soap bubbles that form between the rods will have edges that join where you should build your roads.
Sorry, no subscription, but isn't strong AI an NP problem? Eek, the implications!
Boy, this sounds exciting. Too bad it'll probably turn out to be nothing so cool if I get to read the full article...
-grendel drago
Laws do not persuade just because they threaten. --Seneca
I can only access the abstract of the article, but isn't the size of the problem they can solve limited to the size of their "microfluid" computer? If so, what's the breakthrough?
If you are allowed to limit the problem size, then you can solve it on a normal computer. All you need to do is make the computer big enough. For instance, you could make a travelling-salesman computer out of a circuit what builds all possible paths in parallel and then use pairwise comparison to find the lowest-cost path.
This assumes the circuit is large enough to hold the whole search space, which is the fatal flaw. Classification of a problem as NP-complete is based on its asymptotic complexity: how the computation time grows as the problem size grows without bound. Put a bound on the problem size, and you haven't solved anything.
It seems to me that the microfluid computer has the same flaw.
Does anyone know more about this? Please straighten me out.
--
Patrick Doyle
Patrick Doyle
I mod down every jackass who puts his moderation policy in his sig. Oh, wait a sec....
A problem X is in the set NP-hard if all problems in NP can be transformed into X in polynomial time. Thus, every problem in NP-hard is at least as hard as every problem in NP.
A problem is in NP-complete if it is in NP and NP-hard. Thus, NP-complete is a "representative" set of NP problems, such that solving one of these in polynomial time would also mean solving all other NP problems.
Here is the FOLDOC entry for NP-hard. It explains all this.
--
Patrick Doyle
Patrick Doyle
I mod down every jackass who puts his moderation policy in his sig. Oh, wait a sec....
I don't think we should fall into the trap of thinking that all problems need to be solved by digital computers. Way back in the 1960's and 70's, engineers were trained in modeling. If you scale the paramaters properly, then you can get a (reasonably) accurate answer from a small test case. Many aircraft designs were tested on a small scale model in water, for instance. looking at the water flow meant that they had all those aerodynamic calculations done, in real time. The best computers on earth at the time would have taken decades to crunch the numbers to get the same result.
The 'DNA Computers' we've been making such a fuss over lately, are essentially just modeling again. If you can sift well, and your modeling parameters are correct, you can run a lot (10^38 anyone?) in a few minutes. (Of course, it may take you weeks or even years to set it up correctly, and the old GIGO rule still applies.)
This seems to be just modeling a class of hard computing problems, and letting reality show us what the answer is. Sometimes, analog is best.
bit of my favorite hooby horse, so I hope you'll excuse me repeating it:
ALL key-based encryption is in NP (it is easy to verify a suggested key). So it matters little whether it is based on factorisation, points on elliptic curve, rotor positions, or S boxes.
BTW I do believe that while nobody knows whether FACTOR is NP, it is commonly held NOT to be NP COMPLETE.
What we want to show is that P = NP, right? Simple! P = NP <=> P/P = NP/P <=> 1 = N. There you have it!
, (ii) parallel searching of all potential solutions by using fluid flow
I couldn't read the article (paid subscription), but this excerpt looks like it's still a brute-force. They were only able to solve in P time by using parallelism.
Does this really count? I'm curious.
General Relativity: Space-time tells matter where to go; Matter tells space-time what shape to be.
I just want to point this out, since it's important, but I believe the definitions state that reducing from one NP-Complete problem to another has to be able to be done in P time.
Trees can't go dancing
So do them a big favor
Pretend dancing stinks!
The inner link goes to PNAS which seems to cost over $100/yr. to subscribe to. Please don't post articles referencing such material.
I've been using microbrew to solve my problems for years...
And the reason that people keep saying that this problem is a simple MST problem is because they are picturing a problem in which all nodes are known.
For this problem picture a three city setup, where each city is the vertex of a triangle. Then the solution to this problem is to have each city connect a road towards a fourth, unknown node somewhere in the middle of the triangle. The NP-edness of this problem comes from the fact that you do not know where the fourth node belongs, and the only way to prove where it belongs is to test all available placements.
The soap bubble will always yield the optimal solution to this because (as you state) of surface tension and energy minimization.
--
"A mind is a horrible thing to waste. But a mime...
It feels wonderful wasting those fsckers."
I currently have no clever signature witicism to add here.
As someone else pointed out, RSA is based on the prime factorization problem, not the discrete log problem. Diffie-Hellman and ElGamal are two public key systems based on discrete logarithms.
at http://www.pnas.org/cgi/content/short/98/6/2961
if you trust me
The article got it wrong, too. Obviously, they didn't have a computer scientist as a peer reviwer. So much for the theory that all scientists are computer scientists...
The editor got it wrong, and so did a number of posters, but here is a quick run down of some major complexity categories:
NP: A problem which can be *verified* in polynomical time. This even includes constant time problems, like, is 5*6=42?
P: problems in NP that can be solved in polynomial time (ie quickly)
NP-hard: those problems in NP that can't be solved in P-time. This is probably what all Slashdotters mean when they say "NP".
NP-complete: a class of problems that all other problems in NP reduce to. One of the biggest open questions in computer science is determining if any NP-complete problem does not reduce to any problem in P (then any NP-hard problem would have any easy solution...)
Whew. Let's get a few things straight. First of all, NP problems are *not* hard by definition. The class of NP problems certainly includes hard problems, but it also includes all of the P problems. Second, solving any old NP problem doesn't mean you've solved all NP problems (after all, we have solutions to lots of P problems and P is in NP). It is only NP-COMPLETE problems that have the property of solving every problem in NP via a poly-time reduction. Third, solving a specific instance of an NP-Complete problem isn't a big deal. I'll make one up right now. The solution to the instance of the CLIQUE problem for n=0 (zero verteces) is false. Wasn't that easy? Solving a specific instance isn't particularly special. You have to solve the *general* problem to grab the big prize (P=NP). Conclusion: Solving a specific instance of an NP problem isn't anything to wet yourself over.
Graph Isomorphism and Factoring are two problems which are neither known to be NP-Complete, nor is any poly time algorithm known for either. I know factoring is in both NP and Co-NP (a certificate can be generated to show that a number has no factors less than n, but don't ask me how). Is there any relation between these two problems? By the "what's clean and elegant is probably true" method of proof, it seems like these should be equivalent. Is graph isomorphism in Co-NP? It seems like it might be possible to generate some certificate that here's some property one of the graphs has but not the other that it might be.
One problem I see with trying to show them equivalent is that one problem takes two graphs, and the other takes a number and an upper bound on the size of the factor (or just a number if you are checking for primality). This makes it difficult to imagine a reduction.
Thoughts?
I read the Scientific American article too, but if you notice the interconnection points, there is the shortest ammount of roadway, not the shortest/fastest paths. Between three points on a triangle, they intersect in the middle, but it isn't the fastest.
No, in order to solve the classic TSP, you need to make it the shortest round trip, not be cheap on the construction materials! To really do a TSP, you need a permutation generator(got one!), and start trying solutions, prune larger nodes off, and skip, and you'll finally have it.
Granted, it's messy, long, and not too elegant(program the PG to skip bad sequences..), but it's the only way I've found to get there. If the soap array generated the shortest routes, instead of optimized materials, I'd agree/apologise. Still, alternative resouces must always be investigated, you never know what's out there. =)
This mind intentionally left blank.
The KKK a bunch of sheetheads? You decide!
-Jon
i wish i had a link so i could get a +1...
Streamripper
this is my sig.
Check out his book "The New Turing Omnibus" for further examples. Incidentally, I recommend this book as one that should be in every hacker's library.
Ceci n'est pas une
> this also means they can do other stuff.
Yes. In fact it means that they can do every single other NP problem. If you can do one, you can do them all. All you have to pay is a measly polynomial time conversion cost. (Of course this polynomial could have HUGE constants in it, but theoretical CS people only care about the O() of a problem.)
"You saved 1968." - Ms. Valerie Pringle to the crew of Apollo 8
I haven't read the article (I don't have an account), but I read part of it which someone posted. What they seem to have done is build a machine (a set of pipes and sensors essentially), which can determine this problem. This machine is not a Turing machine, and thus most (if not all) theorems about time complexity or whatever don't apply. This reminds me of a piece in Cryptonomicon where someone was building a machine specifically for solving differential equations, and then Turing comes along and builds a machine which can solve any algorithmic problem. Are we now going back to building porblem-specific machines, i.e. the Dark Ages?
my last question was: "where did you hear about this, and where can i find more?" thanks in advance...
--
Peace,
Lord Omlette
ICQ# 77863057
[o]_O
Yeah, I was trying to express that idea in context with the question without getting too involved. I've studied big O and little O. Sorry, if my answer wasn't satisfactory. FOR A COMPUTER, you don't solve NP problems. Not classically. And STILL, you wouldn't have strong AI. It was a decent question, but I was saying... no, this won't do that. And I am pretty sure that I answered his AI problem in context, no offense.
Eh...
Who the hell even remembers me to call me a karma whore anymore. I've been so busy with school that I can barely take the time to post and then reexplain myself the idiots that flood this site.
Eh...
No, an NP problem is a computational (supposed) impossibility. (or really hard). As in, the formula is insanely hard. AI problems usually center around "what is it exactly that we should be doing to solve this problem." Or in some cases lookahead, or scalability. A large neural net falls into the catagory that you are thinking of, or lookahead in a chess game. That's only solved by having more ram and more processor speed. Passing the Turing test is just a question of finding a good system to do it with.
Eh...
You write a computer program that solves a handful of NP problems, and call me when if finishes running, ok?
Eh...
With all due respect... yeah, it would be kind of tacky, but this is a reputable organization, probably many readers are members.
ACM (Association of Computing Machinery) charges hundreds of dollars in professional dues for membership, but it's money well spent if you are seriously interested in the profession or, in many cases, NEED truly up to date information.
I don't see any problem with pointing to an articly on NAS(proceedings are proceedings people)... Just don't point to one on Tabloidfor$50.com
Eh...
I think this is a well-known example of an analog computer and years ago (back when they were still a good magazine) Scientific American covered this topic in an issue. They specifically pointed out that the soap bubbles aren't really going to solve the problem since they get into a local minimum and there's just not enough of a difference to force it to the global min. Vince
Also, it will never validate the educational postulate that the famous philosopher Wesley Snipes offered in the critically acclaimed movie 'Passenger 57' that we should "Always bet on black."
I want my tax money back.
Game: Player 'Donald J Trump' now has AI skill level 'experimental'.
Happen to have read this article yesterday while browsing journals/killing time...anything (Harvard chemist) Whitesides writes is must read. But authors emphasize this is a toy (n = 6) problem: don't try scaling this to (e.g.) scheduling 1,000 airliners.And if one airliner breaks down,what do you do: tell the other 999 to sit still while you whip up another microfluidics array...?
nemesys
The clay institute $1m award is more so based on acceptance by the math community then it is on a solution. This reminds me of a story a math teacher told me. Something about a man who applied for membership in some American Math Society and was turned down. So he went back to europe and a few years later he returned and applied again, but this time he had a simple equasion that showed .999_ (repeating decimal) equalled 1. I also recall the story of Newton where he was dismissed by his colleagues and even an attempt to steal his discovery. And there are many other such histories ...
So for an award based more so on acceptance than on solution, it sounds to me that the Clay Institute will have plenty a way to so no. And in the event they ultimately cannot say no, then they can change the rules and awards at will it seems given their "rules".
3 S.E.A.S - Virtual Interaction Configuration (VIC) - VISION OF VISIONS!
My colleagues routinely solve hard max-clique instances involving several hundred vertices on PCs. See, for example, the now 8-year-old 2nd DIMACS Challenge for more details including performance on specific instances.
cluster of these thing would be very useful for the maximum clique of Slashdot users
only infrmatn esentil to understandn mst b tranmitd
This one caught my eye because I actually worked on the clique detection/maximal common subgraph & finding subgraph isomorphisms for my Ph.D. It turns out these NP-complete problems are directly applicable to the searching of chemical databases. The basic problem is this: given a query molecule A and a database molecule B, does B completely contain A? This is the problem of subgraph isomorphism. Finding a subgraph in the case of a single pair of molecules is tough, especially if the molecules are large. Now imagine running a query aginst a large database of patented molcules (CAS online- tens of millions of structures). The stakes are high since patents on pharm molcules can be worth billions; the research to find them can cost similar amounts of money and take years. Now to take a step back. If a method was found to solve ANY NP-complete problem in polynomial time it would mean NP=P since the NP-complete problems form an equivalence class. NP=P? is one of the foremost unsolved questions of mathematics. My guess is someone has found a trick to solve certain NP problems quickly under specific conditions. This is nothing new, in fact, in my case, I showed that a massively parallel computer (Distributed Array Processor 4,096 1 bit processors with a taurus geometry) can be used to solve subgraph isomorphism quickly for specific cases.
Simple fluid computers were used on the Apollo missions to calculate trajectories. Nice to see that this branch of computer design never really went away.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~ the real world is much simpler ~~
--- -- - -
Give me LIBERTY, or give me a check.
- People read the articles before posting.
- Slashdot editors turned 30 seconds of their time toward making sure people can read the articles.
With that said, you can see aI don't know much of the specifics, but this doesn't seem to be an incredibly interesting development. Since "three-dimensional microfluidic networks" are not quantum-mechanical in nature, at best whatever they can do is to more
What does this mean for you? That this evolution is not interesting and does not shed new light on anything in the physical or mathematical world: nowhere does the article say that this system will solve in polynomial time the maximum clique problem. NP doesn't mean a problem is unsolvable: just that it becomes increasingly and increasingly difficult to solve as the size of it increases. Here is an introduction to the idea of NP. The clay institute is offering $1m for anyone that can solve NP, so I doubt this article claims to do anything of the sort, although, as we've all by now noticed, I can't actually see the article itself. Not worth $5 if you ask me.
Here is an article that already proposes DNA computing. (.gz, and probably not worth a d/l)
And here are some other NP problems
Anyone feel like paying their one-time fees and setting up a mirror?
Cyclopatra
"We can't all, and some of us don't." -- Eeyore
"We can't all, and some of us don't." -- Eeyore
I believe that 'dude' was Leonard Adleman ('A' of RSA infamy)
Check out the papers at the USC Laboratory for Molecular Science
It's a statistical technique, which is never guaranteed to find a solution (I believe) but takes advantage of the huge number of molecules available to speed up the brute-force search. Unfortunately, I have no idea what it's time complexity is, nor how it compares to this technique (not paying for a subscription today :)
Living better through chemicals
"And thus the Holy Grail of the Hollywood InfoTainment Digeratti was found to have yet another dent upon it's glistening face. And it was good."
"And the Open Source Angels did sing with rejoice in their hearts and lo thier song carried upon the net...'YOU CANNOT SECURE DIGITAL CONTENT'"
shutdown -now
"A microprocessor... is a terrible thing to waste." --
"A microprocessor... is a terrible thing to waste." --
GeneralEmergency
This article just goes on to show how many of the computer science problems and mathematical problems can be solved with the help of physical scientists (note: not only physics, but chemistry also as in this case!). This goes along with research efforts at the University of Chicago to builder wires that are a strand of conductive molecules long. They can potentially solve a lot of mathematical problems by designing circuits that accomplish what they want. (For example, you can put a "junction" , where a signal gets split between to strands of molecules. Then one can flip the switch by sending photons to the junction!)
God first, wife second, math third, and physics fourth. Wait
God first, wife second, math third, and physics fourth. Wait
God first, food second, wife third...
Don't forget that as an option you can get Office bundled with it... Windows NP-complete.
"My mother works for Microsoft now. A whole other cult."
I think your problem is not the "maximum" but the minimum clique problem. I believe the answer is three; the jocks, the stuck-ups, and the geeks. Definitely an NP problem, but I don't see that it is NP-hard.
"My mother works for Microsoft now. A whole other cult."
... slashdot must remove this AC post. The E-meter is based on this NAS paper.
"My mother works for Microsoft now. A whole other cult."
Just to point out that NP is actually a superset of the class P, the problems of which can be solved in polynomial time. These include some pretty simple problems (i.e. linear equations). So, to associate hardness with the class NP is not accurate by the definition. difficult != NP. However, a *different* class of problems, those that are NP hard, are theoretically difficult in that any problem in NP can be polynomial-time reduced to them, even if the problem itself is not in NP. A subset of the class NP hard is the class of problems which are NP complete . If these problems had polynomial-time solutions, then all NP problems would also have polytime solutions. Pardon my regurgitation of formal language thoery 101 :)
NP (definition) Definition: The complexity class of decision problems for which answers can be checked by an algorithm whose run time is polynomial in the size of the input. Note that this doesn't require or imply that an answer can be found quickly, only that any claimed answer can be verified or refuted quickly. "NP" is the class which a Nondeterministic Turing machine accepts in Polynomial time. See also P, NP-complete, NP-hard, PSPACE, coNP, big-O notation, polynomial-time algorithm. Note: For instance, a "yes" answer to the question, "is there a Hamiltonian cycle, or tour, of a certain graph?" can be quickly checked given a certificate for the answer. We can quickly check that the path which is the certificate, indeed, starts and ends at the same vertex, contains every other vertex exactly once, and only uses valid edges. Another example is that a purported sorting of an input can be verified in O(n2). This can be done by sorting the input (again), then comparing it with the purported sorting. NP-complete (definition) Definition: The complexity class of decision problems for which answers can be checked for correctness, given a certificate, by an algorithm whose run time is polynomial in the size of the input (that is, it is NP) and no other NP problem is more than a polynomial factor harder. Informally, a problem is NP-complete if answers can be verified quickly, and a quick algorithm to solve this problem can be used to solve all other NP problems quickly. See also NP-hard, PSPACE, AP. Note: A trivial example of NP, but (presumably) not NP-complete is finding the AND of two boolean bits. The problem is NP, since one can quickly verify that the answer is correct, but knowing how to AND two bits doesn't help one quickly find, say, a Hamiltonian cycle or tour of a graph. So AND is not NP-complete (as far as we know). Author: PEB NP-hard (definition) Definition: The complexity class of decision problems that are intrinsically harder than those that can be solved by a nondeterministic Turing machine in polynomial time. When a decision version of a combinatorial optimization problem is proven to belong to the class of NP-complete problems, which includes well-known problems such as satisfiability, traveling salesman, bin packing, etc., an optimization version is NP-hard. See also strongly NP-hard, PSPACE, AP. Note: For example, "is there a tour with length less than k" is NP-complete: it is easy to determine if a proposed certificate has length less than k. The optimization problem, "what is the shortest tour?", is NP-hard, since there is no easy way to determine if a certificate is the shortest. Another example of an NP-complete problem is to decide if there exist k star-shaped polygons whose union is equal to a given simple polygon, for some parameter k. The optimization problem, i.e., finding the minimum number (least k) of star-shaped polygons whose union is equal to a given simple polygon, is NP-hard. From Algorithms and Theory of Computation Handbook, page 19-26, Copyright © 1999 by CRC Press LLC. To appear in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.strongly NP-hard (definition) Definition: The complexity class of decision problems which are still NP-hard even when all numbers in the input are bounded by some polynomial in the length of the input. See also NP-complete, NP, AP. Note: From Algorithms and Theory of Computation Handbook, page 34-18, Copyright © 1999 by CRC Press LLC. To appear in the Dictionary of Computer Science,Engineering and Technology, Copyright © 2000 CRC Press LLC. Author: CRC-A
I thought we had enough false definitions.
Microsoft announced that their newest version of Windows will be renamed to Windows NP, for Windows Very Hard.
-- Nerds on toast in the new millenium
Unfortunately, this system is not (yet) practical for use in solving actual hard NP problems. From the article's conclusion:
The strength of this microfluidic system as an analog computational device is its high parallelism. Its weakness is the exponential increase in its physical size with the number of vertices. This space-time tradeoff is reminiscent of the limitations of using DNA for solving large NP problems (refs. 5-7). We estimate that the largest graph that might be solved with our algorithmby using 12-inch wafers (commercially available) and 200-nm channels (within the range of photolithography)is 20 vertices. If we use space more efficiently by encoding subgraphs in a plane and use the third dimension for fluid flow, we might solve 40-vertex graphs. By using a computer capable of performing 109 operations per second, a 40-vertex graph can be solved in about 20 min, which makes this microfluidic approach (in its current form) impractical to compete with traditional silicon computers for solving large search problems.
main(c,r){for(r=32;r;) printf(++c>31?c=!r--,"\n":c<r?" ":~c&r?" `":" #");}
They should have slashcode when someone gets a first post, then delay stories 1-2 hours for them for a solid month. They'll probably get bored and go away.
It seems to me like they are just moving the problem into the hardware area. I.e. the size of the hardware grows exponentially, rather than computation time. Moreover, it's not clear from the article that the computation time wont grow exponentially either. I'm assuming that it won't, but these things are pretty tough to prove, and would require building a large number of these devices, each suited for a different # of vertices, and then graphing the computation time. Even that wouldn't be conclusive.
So those of you worrying about AI can relax a bit. Also, building hardware which solves a single algorithm with no abstract constants is not particularly useful for taking over the world, simulating thought, etc.
There might be some applications to decryption, if the size of the key is fixed, etc. But they'll have to build a different "computer" as the key-size grows. Wont be a problem for the NSA though...
When in doubt, have a man come through a door with a gun in his hand.
But let's assume that some computation really does take more than polynomial time. Or, let's even assume it takes a really high polynomial, like N^1000 steps for a problem of size 10, as you yourself suggest. Can physics help us?
Not really. Let's say you want to solve a problem of size 10. That's 10^1000 steps. Let's take a good macroscopic number of atoms, say 10^24. Let's say that all these atoms even interact simultaneously and that each interaction is a computational step, that's 10^48 steps. Let's assume that each step takes 10^-15 seconds. So, we can now perform 10^63 computations per second. Now, 10^1000/10^63 is still 10^937, or 10^928 years, or 10^919 billion years. I'm not willing to wait around for that answer. And, so far, it appears that even quantum computing isn't going to help us out of this one.
(1) The degree to which QM helps with computation is an open question. (2) The authors don't claim that QM is relevant to their problem. (3) QM hasn't been "proven"; in fact, it's pretty much accepted that QM cannot be a complete and correct physical theory. (4) Having a working computer for the six node case tells you nothing about complexity or whether the approach works for larger systems (and using any analog system algorithmically itself is fraught with problems when it comes to defining "solve"). (5) The article itself says that their computer grows exponentially in size, so what they actually came up with is an exponentially sized circuit to solve an NP hard problem in less than an exponential number of steps, which is not the same as solving NP complete problems in polynomial time.
Such a network may solve an NP complete problem quickly under an idealized model of fluid dynamics. However, the real world does not obey idealized fluid dynamics. It doesn't obey it in theory, and it doesn't obey it in practice. Fluid dynamics is a convenient approximation that breaks down at some point.
It's am embarrassment to see this kind of nonsense come out of Harvard. There are lots of people there who should know better. This isn't a problem with some obscure point in the physics of computation, it shows a pretty fundamental misunderstanding of physical theory by a physicist.
Well, I managed to get a hold of the full article. It turns out that their circuits are exponential size and the largest problem they can solve even using optimistic assumptions is of size 20 (if that). So, they didn't even manage to solve the problem in polynomial time using fluid dynamics, they are merely confused about the meaning of the term "NP complete" and "polynomial time" (which refer to complexity on a Turing machine, not circuit depth). In their introduction, they also make lots of mistakes in the definition of NP completeness.
These people don't know what they are doing, and they don't seem to have found anything interesting as far as I can tell. Just ignore it. As far as I know, not all articles in PNAS are peer reviewed; this one should have been.
If the solution scales exponentially with the size of the problem, then it is no solution. Exponential complexity of all known algorithms is the very fact that makes NP-hard problems intractable. Using the word NP in the title is damnable sensationalism, suggesting that progress has been made on theoretical computer science's biggest open problem when in fact the article has no bearing on NP-completeness at all.
because anything exponential in size is necessarily also exponential in time.
First of all, this linked to an article that costs money to see. That's bad. There's a reason they call a site slashdotted when it goes down because of too much traffic. I bet the people who charge for that stuff made a few more bucks than usual today.
Second, was this really such a big deal? We all know that this NP-hard business has a lot to say for encryption. But I for one don't know very much more. If this a minor academic breakthrough with little practical relevance, did it really deserve to be posted? I admit that before reading these posts I didn't know if this report would have anything to say for cryptographic security or not. Can't really expect Hemos to either (especially since he probably hasn't read the article)
A third and much more serious issue is that apparently the page in question wants your credit-card number as password. If this is sent unencrypted across the net (and I saw nothing to indicate this wasn't the case) then some clever guy could take advantage of the slashdot effect to grab a couple of credit card numbers.
The entire submission might be a plot to do excactly this. I don't really believe this, but it is a possibility in this scenario.
xkcd is not in the sudoers file. This incident will be reported.
Unfortunately, you need to infer the definition of the problem from his description of the solution. I originally thought it was an MST as well, but as SLi points out it sounds like it is a Steiner tree problem. To be exact, a Euclidean Steiner tree problem, which is in NP-hard.
you've got a solution to a particular version of the minimum spanning tree problem (the points are all located in 2-D eucludian space, which is not necessarily true for general problem).
So it would seem that this is not an MST problem. Additionally, the fact that the graph is embeddable in a 2D Euclidian space does not make a difference. MST is in P, regardless of the weights assigned to the edges.
"The only rights you have are the rights you are willing to fight for."
I jumped down the wrong persons throat on that one. Lets redirect those words to annoymous coward
what?