## Euler's Partition Function Theory Finished 117 117

universegeek writes

*"Mathematician Ken Ono, from Emory, has solved a 250-year-old problem: how to exactly and explicitly generate partition numbers. Ono and colleagues were able to finally do this by realizing that the pattern of partition numbers is fractal (PDF). This pattern allowed them to find a finite, algebraic formula, which is like striking oil in mathematics."*## Submission + - Safe Cracking Robot->

mschaffer writes:

Link to Original Source

*Kyle Vogt and Grant Jordan built this safe cracking robot in 2006. It’s designed to open any safe that uses a Sergent and Greenleaf 8500 series lock. These locks are classified as “manipulation proof” by the manufacturer.*

Well, I guess this the locks are still "manipulation proof" as they were only able to open the safe with the correct combination.Well, I guess this the locks are still "manipulation proof" as they were only able to open the safe with the correct combination.

Link to Original Source

## Submission + - HTTP is "broken" with critical DDOS flaw, say rese->

huzur79 writes:

Link to Original Source

*Researchers from Proactive Risk, an IT security firm, will demonstrate at an upcoming application security conference a systemic flaw in the HTTP protocol that can easily be exploited through online gaming and other activities into distributed denial-of-service (DDOS) attacks that can flood web servers — even through secure connections — with very slow "POST" traffic that is difficult to distinguish from legitimate traffic, making it hard to prevent.*

The demonstration will come November 8th at the OWASP 2010 conference in Washington DC and is led by researcher Wong Onn Chee, who first discovered the attack last year in Singapore, according to a report from Dark Reading, a security-focused web site. The technique can crash both IIS and Apache servers using either HTTP or HTTPS protocols, and could conceivably affect anything using a web connection, including SSL, VPN and other "more secure" systems.

http://www.darkreading.com/vulnerability_management/security/attacks/showArticle.jhtml?articleID=228000532

http://www.proactiverisk.com/

http://www.owasp.org/index.php/OWASP_AppSec_DC_2010The demonstration will come November 8th at the OWASP 2010 conference in Washington DC and is led by researcher Wong Onn Chee, who first discovered the attack last year in Singapore, according to a report from Dark Reading, a security-focused web site. The technique can crash both IIS and Apache servers using either HTTP or HTTPS protocols, and could conceivably affect anything using a web connection, including SSL, VPN and other "more secure" systems.

http://www.darkreading.com/vulnerability_management/security/attacks/showArticle.jhtml?articleID=228000532

http://www.proactiverisk.com/

http://www.owasp.org/index.php/OWASP_AppSec_DC_2010

Link to Original Source

## Comment Re:Testing Slashdots Methods for Anonymization (Score 3, Funny) 36 36

There are many bits of information we can glean!

- Your "anonymous" name, #34103516
- Date and Time: (Tuesday, November 02 @ 6:04PM)
- You were one of the first posts so you probably read Slashdot often. Also, you probably visit Slashdot regularly around 6:00 PM.
- Writing Style: Short messages, funny

So I could search for regular Slashdot users who tend to be active around 6:00 PM, post brief messages, and are often one of the first to comment. Narrow down that list to users who actually did log in on 11/02/2010. Since, we know that you did read this article there is also a decent chance that you commented on this article with your actual user name.

We will find you!

## Comment Re:Solving a different problem (Score 1) 394 394

Whoops, you are correct. Euclidean Traveling Salesman is NP-Complete. I missed an important reference (http://portal.acm.org/citation.cfm?id=290179.290180) when I was reading about the Euclidean Traveling Salesman Problem.

I had been thinking of a scheme where you essentially would add a tunnel between each pair of flowers, and artificially constrain the paths so that the bees have to travel through the tunnels. You could then artificially make the lengths of some of the tunnels longer than others. However, because ETSP itself is NP-Complete we could reduce factoring to ETSP directly.

I would agree that there could potentially a few useful heuristic's for ETSP that we could learn from the bees, but I highly doubt that any of these heuristics will actually allow us to solve the really hard instances.

I had been thinking of a scheme where you essentially would add a tunnel between each pair of flowers, and artificially constrain the paths so that the bees have to travel through the tunnels. You could then artificially make the lengths of some of the tunnels longer than others. However, because ETSP itself is NP-Complete we could reduce factoring to ETSP directly.

I would agree that there could potentially a few useful heuristic's for ETSP that we could learn from the bees, but I highly doubt that any of these heuristics will actually allow us to solve the really hard instances.

## Comment Re:Solving a different problem (Score 1) 394 394

Besides this, there are several other problems with the claim that bees can solve the Traveling Salesman Problem (TSP). The experiments actually show that bees can solves some 'average' instances Euclidean Traveling Salesman Problem (ETSP).

- 1. Euclidean Traveling Salesman is probably not NP-Complete.
- 2. In fact there is a PTAS (polynomial time approximation scheme) for ETSP so the bees could be computing approximate solutions to ETSP.
- 2. Even if we were solving the standard TSP we are only solving it for 'average' case instances. Just because you can solve 'average' case instance doesn't mean you can solve arbitrary instances. With a few exceptions 3-SAT solvers tend to work well for many 'average' case instances.

I propose a new experiment:- 1. We can pick a hard cryptographic problem (say factoring a number N). We can take our specific instance N from some large public RSA key.
- 2. We can easily reduce factoring to TSP to get some specific TSP instance T. This ensures that we pick a hard TSP instance (either that or factoring N and breaking RSA wasn't that hard in the first place). Note that these distances are not necessarily Euclidean!
- 3. Add a flower for each vertex in T
- 3. Artificially constrain the pathways between flowers so that only direct path between two flowers has distance corresponding to the length of this edge in T.
- 4. See what solutions the bees find now.
- 5. If the bees do actually find the optimal TSP solution to T then we can use this solution to easily recover the factors of N.

## Comment Breaking RSA (Score 1) 394 394

I would suggest the following experiment:

- 1. Pick the RSA key (N=pq) for some large company (say ebay)
- 2. Reduce the problem of factoring N into a traveling salesman instance.
- 3. Let bees find the solution to traveling salesman instance.
- 4. Recover p,q from this solution
- 5. Profit

## Comment Re:What would the impacts of this be for cryptogra (Score 1) 457 457

Probably, but in reality people have constructed crypto schemes from slightly stronger assumptions (like existence of trapdoor, one way functions, etc). I don't think anyone has ever created a crypto scheme which would be provably NP-hard to break (ie, an efficient algorithm to break the crypto scheme would yield an efficient algorithm to solve any NP-complete problem). This is an open question. One challenge is that P!=NP says that some problem instances are hard, but for crypto you can't just say that some messages are hard to crack. You have to say that "all encrypted messages" (more realistically all but a "negligible fraction" of encrypted messages) are hard to break.

## Comment Re:this is going to create history (Score 4, Interesting) 457 457

IMO, The P vs NP is fundamentally more tricky than other famous theorems/conjectures (like FLT), because on some level it is a statement about mathematics itself. The assumption that P != NP on some level implies that the finding mathematical proofs is difficult. This means that if P!=NP it may be even more difficult to prove that P!=NP. It has been shown that assuming one-way functions exist (this would imply P!=NP easily enough) that a certain type of proof called "natural proofs" can never be used to separate P from NP.

On the flip side, showing P = NP could be easier, but most people believe this is false, since it would mean that there is essentially one "master algorithm" that can solve any problem in NP efficiently.

The current state of computational complexity theory is that we are no where close to resolving P!=NP, that is unless this proof actually checks out. Honestly, we can't even settle "easier" questions like P vs PSPACE. The implications of a correct proof would be absolutely mind blowing.

On the flip side, showing P = NP could be easier, but most people believe this is false, since it would mean that there is essentially one "master algorithm" that can solve any problem in NP efficiently.

The current state of computational complexity theory is that we are no where close to resolving P!=NP, that is unless this proof actually checks out. Honestly, we can't even settle "easier" questions like P vs PSPACE. The implications of a correct proof would be absolutely mind blowing.

## Comment Re:'limousine liberalism' (Score 1) 589 589

I would agree with you that money spent on R & D is not money wasted, but I think the EV/Computers analogy breaks down in several ways.

First, Moore's law will not necessarily apply to the development of battery technology. Moore's law has been amazing and awesome. In my humble opinion one of the major forces behind this rapid growth in the speed of the processor was the processor itself. It would be very difficult to design a chip by hand, but once you have a processor to run some optimizations automatically and build a better chip. Of course once you've built a more powerful processor you can use it to help design even better chips etc... I don't see how this cycle would apply to batteries....

I personally think that R & D is never wasted (unless we know for certain that we can't achieve the goal). Maybe the new technology will drive down the cost of EV's while making them more convenient, maybe it won't. Even if it doesn't we still may end up developing new technologies in other areas. I say its worth it.

First, Moore's law will not necessarily apply to the development of battery technology. Moore's law has been amazing and awesome. In my humble opinion one of the major forces behind this rapid growth in the speed of the processor was the processor itself. It would be very difficult to design a chip by hand, but once you have a processor to run some optimizations automatically and build a better chip. Of course once you've built a more powerful processor you can use it to help design even better chips etc... I don't see how this cycle would apply to batteries....

I personally think that R & D is never wasted (unless we know for certain that we can't achieve the goal). Maybe the new technology will drive down the cost of EV's while making them more convenient, maybe it won't. Even if it doesn't we still may end up developing new technologies in other areas. I say its worth it.

## Comment Re:Barred for 20 years? (Score 1) 72 72

If they mislead customers again during the next 20 years then they will again be barred from misleading customers.

## Comment Re:So? (Score 1) 691 691

If you look at the judicial watch report, it is clear that the judge (or close family members) had many more investments. So it seems that not too much of the judge's livelihood depended on the oil investments. Still though, you would hope that the judges personal holdings didn't influence the judge's decision in any way.

## Submission + - SPAM: Delta delivers two children to wrong cities due to

## Submission + - Judge limits DHS laptop border searches->

An anonymous reader writes:

Link to Original Source

*A federal judge has ruled that border agents cannot seize a traveler's laptop, keep in locked up for months, and examine it for contraband files without a warrant half a year later. The ruling apparently says searches at the border are permissible, but that a warrant is required to seize the device for later examination.*Link to Original Source