Is there any calculation that current processors cannot calculate ?

[Modelworks]

I got into a discussion the other day about a companies servers that the IT said the technology wasn't there to keep up with the needs of the company. I told him it was their budget not that the technology didn't exist.

It wasn't anything major , just a database server with a couple hundred clients.

But , that got me to thinking.
Is there anything the we don't have enough cpu power to calculate ?
I'm not talking about things that are researched just for the sake of doing it, like prime numbers, but things like dna sequencing.

If you toss out the budget requirements, is there any calculation that is so massive that we just don't have the processor tech to get a answer in a reasonable (within a year) time frame ?

 

[firewolfsm]

Plenty. Take an incredibly complex protein and even with distributed computing AND massive servers you won't get an answer in a reasonable time. We only fold the proteins we can as computers get faster in simulations.

There are also many many more, that's why we're working on Quantum Computing in the first place.

 

[bsobel]

If you toss out the budget requirements, is there any calculation that is so massive that we just don't have the processor tech to get a answer in a reasonable (within a year) time frame ?

Public key encryption is based on the fact that we don't have enough processing power to break it. Thats a somewhat self referential but true problem.

 

[sdifox]

P and NP. There are problems that can not be solved efficiently. Those are known as NP (not possible) problems.

http://en.wikipedia.org/wiki/NP-complete


http://for.mat.bham.ac.uk/R.W.Kaye/minesw/ordmsw.htm

 

[Cogman]

Traveling Sales man with 1000000 nodes. Or, like sdifox said, NP Hard problems.

 

[f95toli]

There are also problems for which there are no efficient parallel algorithms meaning the speed by which they can be solved is effectively limited by the speed of a single CPU (or DSP) which can be a serious problem in certain applications.
Multi-user detection for 3G/4G is -as far as I know- one such example.

 

[silverpig]

There are plenty of simulations you can run at very low resolution today that we would love to bump up the resolution on in order to be more accurate but can't because of the lack of processor power.

 

[sdifox]

Originally posted by: Cogman
Traveling Sales man with 1000000 nodes. Or, like sdifox said, NP Hard problems.

Travelling salesman just takes time to calc, it is still doable. And not even a lot of time.

That is what GIS is.

My ex GIS team used to do monthly calc of road distance of schools (from school to school) within a school board (for the whole province). That is about a week of running on a dual dual core opteron.

 

[CycloWizard]

Originally posted by: sdifox
Travelling salesman just takes time to calc, it is still doable. And not even a lot of time.

That is what GIS is.

My ex GIS team used to do monthly calc of road distance of schools (from school to school) within a school board (for the whole province). That is about a week of running on a dual dual core opteron.

Did you solve it deterministically or just heuristcally? Both can be done, but the time required for each is likely vastly different. 10^6 nodes isn't bad, but the number of permutations for a deterministic solution increases dramatically as the number of nodes increases.

 

[dinkumthinkum]

Originally posted by: sdifox
P and NP. There are problems that can not be solved efficiently. Those are known as NP (not possible) problems.

Eeek!! Way off dude. Did you ever read those links yourself?

P stands for Polynomial-time. This means there is an algorithm on a Deterministic Turing Machine which worst-case solves the problem in polynomial time, if the problem is in P.

NP stands for Non-deterministic Polynomial time. This means there is an algorithm on a NON-deterministic Turing Machine which worst-case solves the problem in POLYNOMIAL time, if the problem is in NP.

And before you jump in with further misconceptions: a NON-deterministic Turing Machine can -- in parallel -- consider many solutions simultaneously and only output the one which gets the acceptance result. Needless to say, no one has managed to create a "real" non-deterministic Turing Machine. It has NOTHING to do with random numbers.

Another way of characterizing NP is that it is the problems which have polynomial-size PROOFS for a given input that they accept it. This is easy to see: simply generate ALL polynomial-size proofs for a given input and use a non-deterministic Turing Machine to check every one in parallel, in polynomial time.

Generally problems outside of P are considered "intractable" which is just a shorthand way of saying that they may take too much time to be practical. But even problems outside of P may have average-case polynomial-time algorithms which are quite useful: Hindley-Milner type inference and checking is a good example. It is PSPACE-complete in its simplest form, but average case is linear time.

The set of NP-hard problems are those problems for which it is the case that every problem in NP can be reduced to them. The NP-complete problems are NP-hard AND also in NP themselves.

And P, NP are just the first two levels of the polynomial hierarchy, which is all part of PSPACE, which is part of Turing-computable. Then there's a whole arithmetic hierarchy of undecidable problems, which no computer will ever be able solve.

So yea...

 

[wwswimming]

a VRML model of all the credit derivatives outstanding & associated with the
credit crisis. showing every mortgage in every mortgage backed security,
to figure out who owes what to whom. i say VRML because it would help to
have it in 3D, so if a town in Norway loses $60 million on mortgage backed
securities they bought from a company in NYC, that type of detail can be
represented.

basically a model to visualize the entire situation. now that the government
is taking on the "toxic" mortgage backed securities, how do you track them ?
how can you evaluate them if you can't dissect them mortgage by mortgage ?

well, maybe you could do it all on a single Skulltrail system.

 

[sdifox]

Originally posted by: dinkumthinkum

Originally posted by: sdifox
P and NP. There are problems that can not be solved efficiently. Those are known as NP (not possible) problems.

Eeek!! Way off dude. Did you ever read those links yourself?

P stands for Polynomial-time. This means there is an algorithm on a Deterministic Turing Machine which worst-case solves the problem in polynomial time, if the problem is in P.

NP stands for Non-deterministic Polynomial time. This means there is an algorithm on a NON-deterministic Turing Machine which worst-case solves the problem in POLYNOMIAL time, if the problem is in NP.

And before you jump in with further misconceptions: a NON-deterministic Turing Machine can -- in parallel -- consider many solutions simultaneously and only output the one which gets the acceptance result. Needless to say, no one has managed to create a "real" non-deterministic Turing Machine. It has NOTHING to do with random numbers.

Another way of characterizing NP is that it is the problems which have polynomial-size PROOFS for a given input that they accept it. This is easy to see: simply generate ALL polynomial-size proofs for a given input and use a non-deterministic Turing Machine to check every one in parallel, in polynomial time.

Generally problems outside of P are considered "intractable" which is just a shorthand way of saying that they may take too much time to be practical. But even problems outside of P may have average-case polynomial-time algorithms which are quite useful: Hindley-Milner type inference and checking is a good example. It is PSPACE-complete in its simplest form, but average case is linear time.

The set of NP-hard problems are those problems for which it is the case that every problem in NP can be reduced to them. The NP-complete problems are NP-hard AND also in NP themselves.

And P, NP are just the first two levels of the polynomial hierarchy, which is all part of PSPACE, which is part of Turing-computable. Then there's a whole arithmetic hierarchy of undecidable problems, which no computer will ever be able solve.

So yea...

lol, he was asking about whether there are problems that current computers can't compute and I pointed him to p-np. What is the problem? Once he gets that, he'll get what he is asking.

 

[sdifox]

Originally posted by: CycloWizard

Originally posted by: sdifox
Travelling salesman just takes time to calc, it is still doable. And not even a lot of time.

That is what GIS is.

My ex GIS team used to do monthly calc of road distance of schools (from school to school) within a school board (for the whole province). That is about a week of running on a dual dual core opteron.

Did you solve it deterministically or just heuristcally? Both can be done, but the time required for each is likely vastly different. 10^6 nodes isn't bad, but the number of permutations for a deterministic solution increases dramatically as the number of nodes increases.

To tell you the truth, I have no idea how ESRI does it I know what they are doing, just how how. I am guessing it's a weighted shortest path system.

 

[Biftheunderstudy]

There are a lot of astrophysics problems which take a long time to compute. I recently went to talk by Tom Abel and their galaxy simulations are run on a 32 processor cluster with ~TB of RAM and it took them a couple of weeks to complete. The code doesn't involve half the relevant physics and the resolution is on the order of a 10000 star cluster. Also, their doing this on GPU's which are orders of magnitude faster than CPU's.

 

[silverpig]

Originally posted by: Biftheunderstudy
There are a lot of astrophysics problems which take a long time to compute. I recently went to talk by Tom Abel and their galaxy simulations are run on a 32 processor cluster with ~TB of RAM and it took them a couple of weeks to complete. The code doesn't involve half the relevant physics and the resolution is on the order of a 10000 star cluster. Also, their doing this on GPU's which are orders of magnitude faster than CPU's.

I wrote a simplified galaxy collision simulator for a computational physics class. It was definitely not as computationally intensive as the one you mentioned, but it wouldn't have been difficult to code it so.

 

[dinkumthinkum]

Originally posted by: sdifox
lol, he was asking about whether there are problems that current computers can't compute and I pointed him to p-np. What is the problem? Once he gets that, he'll get what he is asking.

The problem is that your reading comprehension is nil. You supplied blatantly -- in fact, embarrassingly -- false information about complexity classes P and NP.

Now smack yourself in the face and start reading the links that you yourself posted.

 

[CycloWizard]

Originally posted by: sdifox
To tell you the truth, I have no idea how ESRI does it I know what they are doing, just how how. I am guessing it's a weighted shortest path system.

There are many ways to attempt to optimize a traveling salesman problem. A "weighted shortest path system" is not one of them. What would you say...ya do here?

 

[sdifox]

Originally posted by: dinkumthinkum

Originally posted by: sdifox
lol, he was asking about whether there are problems that current computers can't compute and I pointed him to p-np. What is the problem? Once he gets that, he'll get what he is asking.

The problem is that your reading comprehension is nil. You supplied blatantly -- in fact, embarrassingly -- false information about complexity classes P and NP.

Now smack yourself in the face and start reading the links that you yourself posted.

What do you mean by false. So I used not possible to compute efficiently as opposed to not in polynomial time, how is it false though? Question is "Is there anything we can't compute with current computer technology" and I mentioned NP-C.

 

[sdifox]

Originally posted by: CycloWizard

Originally posted by: sdifox
To tell you the truth, I have no idea how ESRI does it I know what they are doing, just how how. I am guessing it's a weighted shortest path system.

There are many ways to attempt to optimize a traveling salesman problem. A "weighted shortest path system" is not one of them. What would you say...ya do here?

Like I said, I never looked into how they do it. And since I never got into that part of math...

 

[dinkumthinkum]

Originally posted by: sdifox

Originally posted by: dinkumthinkum

Originally posted by: sdifox
lol, he was asking about whether there are problems that current computers can't compute and I pointed him to p-np. What is the problem? Once he gets that, he'll get what he is asking.

The problem is that your reading comprehension is nil. You supplied blatantly -- in fact, embarrassingly -- false information about complexity classes P and NP.

Now smack yourself in the face and start reading the links that you yourself posted.

What do you mean by false. So I used not possible to compute efficiently as opposed to not in polynomial time, how is it false though? Question is "Is there anything we can't compute with current computer technology" and I mentioned NP-C.

I already answered this. Go back up and read it again.

 

[superunknown98]

Heh, nobody mentioned the weather? To accuratly predict the weather would require alot of power.

 

[CycloWizard]

Originally posted by: superunknown98
Heh, nobody mentioned the weather? To accuratly predict the weather would require alot of power.

Yes, but if I had an infinite budget, I could solve the relevant conservation equations using highly parallelized algorithms since they are generally solved using finite differences. The only thing missing is a larger number of processors that would allow you to solve a more refined mesh.

 

[Kyteland]

Originally posted by: sdifox

Originally posted by: dinkumthinkum

Originally posted by: sdifox
P and NP. There are problems that can not be solved efficiently. Those are known as NP (not possible) problems.

Eeek!! Way off dude. Did you ever read those links yourself?

P stands for Polynomial-time. This means there is an algorithm on a Deterministic Turing Machine which worst-case solves the problem in polynomial time, if the problem is in P.

NP stands for Non-deterministic Polynomial time. This means there is an algorithm on a NON-deterministic Turing Machine which worst-case solves the problem in POLYNOMIAL time, if the problem is in NP.

And before you jump in with further misconceptions: a NON-deterministic Turing Machine can -- in parallel -- consider many solutions simultaneously and only output the one which gets the acceptance result. Needless to say, no one has managed to create a "real" non-deterministic Turing Machine. It has NOTHING to do with random numbers.

Another way of characterizing NP is that it is the problems which have polynomial-size PROOFS for a given input that they accept it. This is easy to see: simply generate ALL polynomial-size proofs for a given input and use a non-deterministic Turing Machine to check every one in parallel, in polynomial time.

Generally problems outside of P are considered "intractable" which is just a shorthand way of saying that they may take too much time to be practical. But even problems outside of P may have average-case polynomial-time algorithms which are quite useful: Hindley-Milner type inference and checking is a good example. It is PSPACE-complete in its simplest form, but average case is linear time.

The set of NP-hard problems are those problems for which it is the case that every problem in NP can be reduced to them. The NP-complete problems are NP-hard AND also in NP themselves.

And P, NP are just the first two levels of the polynomial hierarchy, which is all part of PSPACE, which is part of Turing-computable. Then there's a whole arithmetic hierarchy of undecidable problems, which no computer will ever be able solve.

So yea...

lol, he was asking about whether there are problems that current computers can't compute and I pointed him to p-np. What is the problem? Once he gets that, he'll get what he is asking.

I think he was referring to the bolded part.

 

[KIAman]

Any real-life simulators. The best we have are approximations of what happens in real life. Some notable examples are weapons simulation, nuclear simulation, medicine simulation, macro economy simulation, particle acceleration, etc.

Because of the enormous amount of variables and calculations based on changing variables based on variables, accurate real-life simulations are impossible. Instead, we use the tried and true method of testing.

 

[Cogman]

Glad I'm taking discrete math, because I just found one while skimming the book.

Heres the problem that can't be solved with current algorithms/processing powerr. Determine if a Program will halt or not (IE, is a program in the state of an infinite loop, or is it just a big loop.)

Can't be calculated no matter how much power you have.