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

Groups > sci.physics > #532408

Re: Mathematician claims breakthrough in complexity theory

Cross-posted to 2 groups.

Show all headers | View raw

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. 

-- 
Jim Pennino

Back to sci.physics | Previous | Next — Previous in thread | Next 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