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."
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.
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?)
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....
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.
, (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.
Actually, it'd be 'Redundant', wouldn't it? Since the 'by' line clearly indicates the post is #1.
Now, this post is Offtopic.
Of course, I could throw in a comment about the article to change that, but I can't seem to actually see the article.
You have requested an item that requires a subscription to PNAS Online.
There may be many reasons not to kill you, but among them is not that you'll be missed by NASA - The Long Kiss Goodnight
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.
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...
"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
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?" `":" #");}
Materials and Methods
Fabrication of Microfluidic System. Our method for the fabrication of a 3D microfluidic system has been described in detail elsewhere (refs. 13 and 14). Briefly, the silicon master was fabricated by first spinning a negative photoresist (SU 8-50 or SU 8-100) onto a silicon wafer, which has been cleaned by sonicating in acetone (5 min) then in methanol (5 min) and dried by baking at 180C (10 min). The photoresist-covered wafer was soft baked (105C for 15 min) to evaporate the solvent, let cool, then placed under a photomask in a Karl Suss mask-aligner (Zeiss) to expose the photoresist. The exposed photoresist was baked (105C for 5 min), then developed in propylene glycol methyl ether acetate to create a master with one level of feature. Masters with two levels of feature were fabricated by repeating this procedure with a different photomask. The masters were silanized in vacuo (in a desiccator) with 0.5 ml tridecafluoro-1,1,2,2-tetrahydrooctyl-1-trichloros ilane
for 12 h. The silanized masters were then used for molding slabs and membranes of poly(dimethylsiloxane) (PDMS). To fabricate the PDMS membrane, a drop of
PDMS prepolymer was sandwiched between the master and a Teflon sheet and was allowed to cure overnight under pressure (10-50 kPa) at 70C. The cured PDMS
membranes and slabs were aligned by using a home-built micromanipulator stage, oxidized in a plasma cleaner (model SP100 Plasma System, Anatech, Alexandria,
VA) for 40 sec at 60 W under [roughly equal to] 0.2 Torr (1 torr = 133 Pa) oxygen, and brought into contact to form an irreversible seal. This procedure of alignment, oxidation, and
sealing was repeated multiple times for the fabrication of a multilayer microfluidic system.
Chemicals. Negative photoresists (SU 8-50 and SU 8-100) were obtained from Microlithography Chemical (Newton, MA), propylene glycol methyl ether acetate from Aldrich, tridecafluoro-1,1,2,2-tetrahydrooctyl-1-trichloros ilane from United Chemical Technologies (Bristol, PA), PDMS prepolymer (Sylgard 184) from
Dow-Corning, fluorescent nanospheres from Molecular Probes, and silicon wafers from Silicon Sense (Nashua, NH).
[...]
Conclusions
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. In comparison to DNA-based computation, this microfluidic system can carry out certain logical operations, such as addition, more naturally. The z-direction flow in the four-layer microfluidic device (Fig. 4) acts as an integrator by adding the beads that arrive at the wells from all of the layers. In contrast, the implementation of an algorithm for DNA-based addition was nontrivial (ref. 8), although a far more direct method for DNA addition has been proposed (ref. 17) and partially implemented (ref. 18).
The algorithm we described here for using fluids to search the parallel architecture of a microfluidic system could also, perhaps, be implemented in a 3D microelectronic circuit. There are, however, several advantages to using microfluidic systems. (i) Fluids can carry fluorescent beads or molecules, thereby making the readout by using parallel optical systems simpler than in microelectronic circuits. (ii) Many different "color" beads/molecules can be used in microfluidic systems, whereas electrons have only one "color"; this feature permits fluidic systems to encode more information than electrical systems. (iii) Microfluidic systems might not require power (our algorithm, for example, can be implemented by using gravity). Advantages of electrical over fluidic systems include ease of use (no clogging of channels) and the high speed at which electrons travel through the circuit (which is important for implementing sequential algorithms). Although clogging is a concern in microfluidic systems, it was not a problem under our experimental conditions, because of the relatively small sizes of the beads used (400 nm or smaller) compared with the widths of the microchannels (50 m or greater).
Another motivation for using microfluidic-based computation is the possibility of integrating fluidic components for controlling complex chip-based microanalytical devices. In addition, computation by using microfluidic systems are complementary to ones based on biological molecules (e.g., DNA) or coupled chemical reactions (refs. 19 and 20). The wells and channels in our 3D microfluidic system, for example, could compartmentalize and transport molecules and reactions for the construction of a chemical or DNA-based computer.
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.
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.
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."