computing breakthrough: exponentially faster, ver 2.0

Original post by Subscriber sonhouse on 28 Jun '18 19:27
https://techxplore.com/news/2018-06-breakthrough-algorithm-exponentially-faster-previous.html

This is an interesting question that I wake up again, thanks sunhouse, because it merits a good answer. From me or from anyone interested in the matter.

We have seen these kind of headlines earlier. Is this the fruit of an journalist not knowing what he is writing about? Or is it something real, something that will revoultionize the world and science of computing?

Is it so general so we can use it everywhere? Like in chess?

Because Chess is a time-consuming calculation. Delivering lots of solutions to a certain problem, reducing it and give the best one. This is what computer Chess is all about. So the Chess is a good example of what this revolutioinizing new algorithm can handle.

Right? Or not?

Or is it just a feather from which a journalist made a hen?

It says;

"this new algorithm samples a variety of directions in parallel. Based on that sample, the algorithm discards low-value directions from its search space and chooses the most valuable directions to progress towards a solution."

When they say the "algorithm samples a variety of directions", they mean "algorithm RANDOMLY samples just a relatively FEW directions" meaning randomly sample just a relatively few (say, just 100) out of a vast number of possibilities (say, one trillion) rather than spend the huge amount of time sampling every one of the vast number of possibilities.
I know what they are talking about because this isn't exactly a totally new idea and is an example of mimicking one of the ways humans often solve problems.
This method does indeed massively reduce the computation time to find a good solution for some classes of problems but at a cost of no longer guaranteeing it will find the BEST possible solution because it no longer looks at ALL the possibilities.

Despite me being unsure if its truly original, I would say this isn't just journalist hype and is indeed a significant 'breakthrough' of a sort but I don't think I can predict about how much practical improvement it will lead to. I cannot say whether it would be fair to say that it would "revoultionize" the world and the science of computing.

Note it can only help with solving certain classes of problems but not others.

Originally posted by @humy
It says;

"this new algorithm samples a variety of directions in parallel. Based on that sample, the algorithm discards low-value directions from its search space and chooses the most valuable directions to progress towards a solution."

When they say the "algorithm samples a variety of directions", they mean "algorithm RANDOMLY samples just a relatively F ...[text shortened]... of computing.

Note it can only help with solving certain classes of problems but not others.

You mean certain classes like sifting through large data sets looking for correlation of some characteristic Vs say calculating 3 body relativistic kind of problems?

Originally posted by @sonhouse
You mean certain classes like sifting through large data sets looking for correlation of some characteristic Vs say calculating 3 body relativistic kind of problems?

Not sure exactly how that method would be 'applied' to 3 body relativistic kind of problems. I will have to think about that one.
As I understand it, what is called the "TWO-body problem in general relativity" is hard enough to solve (let alone some kind ot "THREE-body problem in general relativity"! ) and so far only approximate solutions have been found, no exact solution. See;

https://en.wikipedia.org/wiki/Two-body_problem_in_general_relativity

By the way, when they talk about "directions" in the context of the OP link about algorithms, they aren't usually talking about the special directions in particular but rather "direction" in a much more generic and abstract way where we consider 2 or more variables, which might have nothing whatsoever to do with the special directions but could be mass, vibration, how fat you are, how 'much' two drags interact etc etc and make a plot of data points with each variable being represented on a graph along a different graph axis and typically a multidimensional graph except if it has more than 3 axis then it is usually far to problematic to represent visually and thus such a 'graph' isn't normally represented visually but as a pure maths construct in which case it is called a "multidimensional network". See

https://en.wikipedia.org/wiki/Multidimensional_network

I had once studied multidimensional networks at university but so long ago that I am afraid I think I have forgotten most of what I learned about them which I think is just terrible! If I can find the time later, I should revise this subject area because it is important; maybe also try and see how it might relate to my current research if at all.

Originally posted by @humy
Not sure exactly how that method would be 'applied' to 3 body relativistic kind of problems. I will have to think about that one.
As I understand it, what is called the "TWO-body problem in general relativity" is hard enough to solve (let alone some kind ot "THREE-body problem in general relativity"! ) and so far only approximate solutions have been found, no ...[text shortened]... se it is important; maybe also try and see how it might relate to my current research if at all.

The two body problem in GR is intractable, in the sense that no general, exact, analytical solution to the problem exists. One can do perturbation theory, or assume that one of the two bodies is massless, but that's about it. I don't think this clever new algorithm will help with numerical solutions to GR.

Monte Carlo algorithms already exist for solving field theory problems in classical physics, so I don't know what this would add.

The type of decision problem chess represents looks like it could be helped by this. I imagine one could do random walks through the decision tree, and just pick the best line as the Principal Variation for a conventional alpha/beta search.

So I think this sounds like it would be useful for decision problems, like chess or the travelling salesman problem, but less useful for function problems like solving GR or factoring large composite numbers.

Originally posted by @deepthought
The two body problem in GR is intractable, in the sense that no general, exact, analytical solution to the problem exists. One can do perturbation theory, or assume that one of the two bodies is massless, but that's about it. I don't think this clever new algorithm will help with numerical solutions to GR.

Monte Carlo algorithms already exist for so ...[text shortened]... lem, but less useful for function problems like solving GR or factoring large composite numbers.

Great. Just what we need, a chess engine rated FIDE 6000......