Follow Slashdot stories on Twitter


Forgot your password?

Comment Re:Very cool, but np-complete? (Score 5, Informative) 48

You can think of our search as randomly trying millions of possibilities and hoping for the best. The reason it's so fast is that we order the random attempts very cleverly and tend to find the answer fast if it is indeed solvable. The algorithm usually terminates because it finds a match or times out; rarely does it exhaust the search space in time. The actual complexity of our system is roughly O(N choose 4) where N is the number of stars in the image. Interestingly, this is polynomial, roughly O(N^4), though probably closer to O(N^5) once verification is added.

In summary: the astrometry problem is not NP-hard when approached like we do.

Disclaimer: I am one of the contributors.

Slashdot Top Deals

I judge a religion as being good or bad based on whether its adherents become better people as a result of practicing it. - Joe Mullally, computer salesman