Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > sci.physics > #532426

Re: Mathematician claims breakthrough in complexity theory

Cross-posted to 2 groups.

Show all headers | View raw

In sci.physics jimp@specsol.spam.sux.com wrote:
> In sci.physics Sam Wormley <swormley1@gmail.com> wrote:
>> Mathematician claims breakthrough in complexity theory
>>> http://news.sciencemag.org/math/2015/11/mathematician-claims-breakthrough-complexity-theory
>>> http://news.sciencemag.org/sites/default/files/styles/thumb_article_l/public/sn-isomorphism.jpg?
>> 
>> 
>>> For days, rumors about the biggest advance in years in so-called
>>> complexity theory have been lighting up the Internet. That?s only
>>> fitting, as the breakthrough involves comparing networks just like
>>> researchers? webs of online connections. L?szl? Babai, a
>>> mathematician and computer scientist at the University of Chicago in
>>> Illinois, has developed a mathematical recipe or "algorithm" that
>>> supposedly can take two networks?no matter how big and tangled?and
>>> tell whether they are, in fact, the same, in far fewer steps than the
>>> previous best algorithm. Computer scientists are abuzz, as the task
>>> had been something of a poster child for hard-to-solve problems.
>>>
>>> "If this is correct it's probably the theoretical computer science
>>> result of the decade," says Scott Aaronson, a computer scientist and
>>> blogger at the Massachusetts Institute of Technology in Cambridge.
>>>
>>> Complexity theory is basically the study of what's hard or easy to
>>> solve with a computer. In it, the key thing is how the number of
>>> steps it takes to solve a problem grows with the size of the input.
>>> Suppose, for example, that you want to determine whether a given
>>> number, 983 or 105227, is prime and cannot be divided by another
>>> number. The number of computational steps in that calculation grows
>>> relatively slowly with the number of digits in the number. Generally,
>>> it grows with the number of digits, n, raised to a fixed
>>> power?something akin to n^2. Expressions like that are called
>>> polynomials, so the problem is said to be solvable in "polynomial
>>> time" and is in the complexity class ?P.?
> 
> This cut and paste might have been of interest had it been posted to
> a mathematics group, but it was not. 

Holy shit, it WAS crossposted to a relevant group, this is utterly
mind boggling. 

-- 
Jim Pennino

Back to sci.physics | Previous | Next — Previous in thread | Find similar | Unroll thread

Thread

Mathematician claims breakthrough in complexity theory Sam Wormley <swormley1@gmail.com> - 2015-11-12 08:57 -0600
  Re: Mathematician claims breakthrough in complexity theory jimp@specsol.spam.sux.com - 2015-11-12 19:11 +0000
    Re: Mathematician claims breakthrough in complexity theory jimp@specsol.spam.sux.com - 2015-11-12 19:40 +0000

csiph-web