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

Groups > sci.physics > #532314 > unrolled thread

Mathematician claims breakthrough in complexity theory

Back to article view | Back to sci.physics

Contents

  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

#532314 — Mathematician claims breakthrough in complexity theory

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.”

-- 

sci.physics is an unmoderated newsgroup dedicated
to the discussion of physics, news from the physics
community, and physics-related social issues.

[toc] | [next] | [standalone]

#532408

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

[toc] | [prev] | [next] | [standalone]

#532426

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

[toc] | [prev] | [standalone]

Back to top | Article view | sci.physics

csiph-web