A Short Guide to Hard Problems

Binary_Bark

Binary_Bark

Forging
Joined
Feb 24, 2016
Messages
41,606
Reaction score
23,504
Location
Midgard
How fundamentally difficult is a problem? That’s the basic task of computer scientists who hope to sort problems into what are called complexity classes. These are groups that contain all the computational problems that require less than some fixed amount of a computational resource — something like time or memory. Take a toy example featuring a large number such as 123,456,789,001. One might ask: Is this number prime, divisible only by 1 and itself? Computer scientists can solve this using fast algorithms — algorithms that don’t bog down as the number gets arbitrarily large. In our case, 123,456,789,001 is not a prime number. Then we might ask: What are its prime factors? Here no such fast algorithm exists — not unless you use a quantum computer. Therefore computer scientists believe that the two problems are in different complexity classes.

Many different complexity classes exist, though in most cases researchers haven’t been able to prove one class is categorically distinct from the others. Proving those types of categorical distinctions is among the hardest and most important open problems in the field. That’s why the new result I wrote about last month in Quanta was considered such a big deal: In a paper published at the end of May, two computer scientists proved (with a caveat) that the two complexity classes that represent quantum and classical computers really are different.

The differences between complexity classes can be subtle or stark, and keeping the classes straight is a challenge. For that reason, Quanta has put together this primer on seven of the most fundamental complexity classes. May you never confuse BPP and BQP again.
Click to expand...

More At: https://www.quantamagazine.org/a-short-guide-to-hard-problems-20180716/
 
And here I thought this was going to be an erectile dysfunction thread! :crylaugh:
 
Why tho?

Seriously, what application does this have in the real world?
 
evilstebunny said:
Why tho?

Seriously, what application does this have in the real world?
Click to expand...

Optimisation of calculations for one. In a multi threading world you want to optimise for time and if you know ahead of the calculations which are harder and which are easier you can ensure that you start the harder stuff first on the bigger processors so that you don't finish 99% of your computations and then start the hardest one last on a single processor or something. It has huge applications.
 
You must log in or register to reply here.
Back
Top
Sign up to the MyBroadband newsletter
X