Wednesday, November 30, 2005
Problems too difficult to solve?
It is fascinating to me that even in this day and age there are still problems we cannot solve at all, or problems we don't know how to solve easily. On the other hand, if we knew how to solve all problems there wouldn't have been many challenges now, would there? Keep in mind that I'm talking more from an I.T background than philosophical. In other words I'm talking about the problems we can (or try to) solve with computers.
Let me explain my ranting about problem solving:
My wife is an auditor and I'm a software programmer. When she came across a specific problem the other day, she thought that I would be her helping hand, until I discovered that it's actually not that easy to solve her dilemma.
The problem is the following:
You have a number of invoice totals, as well as one or more grand totals. Some (or all) of the invoices make up some (or more) of the grand totals when you add them together. You need to figure out which invoices make up which totals. I suppose this is needed mostly because of lost or incomplete documentation, but it's the job of the auditors to match these totals.
Consider this example:
Invoice 1: 35.55
Invoice 2: 865.23
Invoice 3: 87.29
Invoice 4: 63.99
Total 1: 99.54
Total 2: 952.52
In this example, we could say that Total 1 is made up of Invoice 1 and Invoice 4 (35.55 + 63.99 = 99.54) and Total 2 is made up of Invoice 2 and Invoice 3 (865.23 + 87.29).
The example above is quite easy. You can solve it by just looking at the values. But consider 100 invoices for example…. Computer to the rescue… or so we thought!
I first tried a brute force way, but the number of combinations just becomes unmanageable for a lot of invoices. If you've got 4 invoices, the total number of combinations to make up a total is 15, but if you've got just 20 invoices, the number of possibilities jump to 1048575! (go figure this one!).
I then tried a more fuzzy approach like genetic algorithms. This approach can get me close to the desired result, but rarely solves the problem completely.
After a bit of investigation, I realized that my problem is very similar (if not exactly the same) as the famous traveling salesmen problem. This opened up a whole can of worms! The computing industry has done a lot of research on problems like this. There is even a whole complexity theory!
I'm not going to go into too much detail now, as it's almost a textbook on its own. My point is just that the more we find out, the more we realize how little we know (if that makes sense!)
Some problems are considered impossible to solve, others can be solved but is very hard. This means that with our finite computing resources, it is not viable to solve the problem in the time we would like. I can for example solve my wife's problem by running 10 computers for 1 week, but it would be futile if they need the answer tomorrow.
One way to try and solve these problems is basically to throw computing power at it. I suppose this is why we invented grid computing. Consider for example the SETI@HOME project. (I suppose this is not the best example for my problem, as SETI has more to do with processing huge amounts of data). A better example might be solving of protein-related diseases like the one also hosted on BOINC. (BOINC actually now hosts a couple of grid computing problems including SETI).
Although throwing more computing power at problems is a good idea, the fundamental problem is that it will always be a limited resource. One thing that might come to the rescue here is something that my little brain still can't grasp and that is quantum computing.
In the computing industry, some technologies actually rely on the fact that some problems are very difficult to solve. Consider most of the encryption standards. They rely on the fact that it is very difficult to compute prime numbers quickly. What do you think will happen if somebody comes up a formula to compute all prime numbers?
Some good advice from me: If you discover a way to solve NP-Complete problems quickly, I suggest to make a visit to the patent office before you tell your buddies!
Some related links if you are interested:
Let me explain my ranting about problem solving:
My wife is an auditor and I'm a software programmer. When she came across a specific problem the other day, she thought that I would be her helping hand, until I discovered that it's actually not that easy to solve her dilemma.
The problem is the following:
You have a number of invoice totals, as well as one or more grand totals. Some (or all) of the invoices make up some (or more) of the grand totals when you add them together. You need to figure out which invoices make up which totals. I suppose this is needed mostly because of lost or incomplete documentation, but it's the job of the auditors to match these totals.
Consider this example:
Invoice 1: 35.55
Invoice 2: 865.23
Invoice 3: 87.29
Invoice 4: 63.99
Total 1: 99.54
Total 2: 952.52
In this example, we could say that Total 1 is made up of Invoice 1 and Invoice 4 (35.55 + 63.99 = 99.54) and Total 2 is made up of Invoice 2 and Invoice 3 (865.23 + 87.29).
The example above is quite easy. You can solve it by just looking at the values. But consider 100 invoices for example…. Computer to the rescue… or so we thought!
I first tried a brute force way, but the number of combinations just becomes unmanageable for a lot of invoices. If you've got 4 invoices, the total number of combinations to make up a total is 15, but if you've got just 20 invoices, the number of possibilities jump to 1048575! (go figure this one!).
I then tried a more fuzzy approach like genetic algorithms. This approach can get me close to the desired result, but rarely solves the problem completely.
After a bit of investigation, I realized that my problem is very similar (if not exactly the same) as the famous traveling salesmen problem. This opened up a whole can of worms! The computing industry has done a lot of research on problems like this. There is even a whole complexity theory!
I'm not going to go into too much detail now, as it's almost a textbook on its own. My point is just that the more we find out, the more we realize how little we know (if that makes sense!)
Some problems are considered impossible to solve, others can be solved but is very hard. This means that with our finite computing resources, it is not viable to solve the problem in the time we would like. I can for example solve my wife's problem by running 10 computers for 1 week, but it would be futile if they need the answer tomorrow.
One way to try and solve these problems is basically to throw computing power at it. I suppose this is why we invented grid computing. Consider for example the SETI@HOME project. (I suppose this is not the best example for my problem, as SETI has more to do with processing huge amounts of data). A better example might be solving of protein-related diseases like the one also hosted on BOINC. (BOINC actually now hosts a couple of grid computing problems including SETI).
Although throwing more computing power at problems is a good idea, the fundamental problem is that it will always be a limited resource. One thing that might come to the rescue here is something that my little brain still can't grasp and that is quantum computing.
In the computing industry, some technologies actually rely on the fact that some problems are very difficult to solve. Consider most of the encryption standards. They rely on the fact that it is very difficult to compute prime numbers quickly. What do you think will happen if somebody comes up a formula to compute all prime numbers?
Some good advice from me: If you discover a way to solve NP-Complete problems quickly, I suggest to make a visit to the patent office before you tell your buddies!
Some related links if you are interested:
- Computing complexity theory
- Constraint Programming (one way to solve complex problems)
- Donald Knuth (this guy is a legend in the computing industry!)
- Quantum Computing
[The software said it required Windows 95 or better, so I installed Linux]
# posted by Jaco Joubert @ 8:30 AM 
Comments:
<< Home
Great post! I found it a really interesting read.
About Quantum computing: You can go and read on how stuff works but it didn't help me much!
What does NP stand for anyway?
About Quantum computing: You can go and read on how stuff works but it didn't help me much!
What does NP stand for anyway?
NP stands for "Non-deterministic Polynomial time". To quote the wikipedia page:
In computational complexity theory, NP ("Non-deterministic Polynomial time") is the set of decision problems solvable in polynomial time on a non-deterministic Turing machine. Equivalently, it is the set of problems that can be "verified" by a deterministic Turing machine in polynomial time.
Hope this makes sense to you!
To get back to the Quantum Computing, consider this part from the howstuffworks site:
Quantum computers aren't limited to two states; they encode information as quantum bits, or qubits. A qubit can be a 1 or a 0, or it can exist in a superposition that is simultaneously both 1 and 0 or somewhere in between.
Now this is where I yawn and crawl back to my hibernation state ;-)
I think this proves how difficult it is for humans to understand something new if you've been "programmed" with older information. This might be why it is so difficult for us to solve these "hard" problems - we are too set in trying to solve problems the traditional way?
In computational complexity theory, NP ("Non-deterministic Polynomial time") is the set of decision problems solvable in polynomial time on a non-deterministic Turing machine. Equivalently, it is the set of problems that can be "verified" by a deterministic Turing machine in polynomial time.
Hope this makes sense to you!
To get back to the Quantum Computing, consider this part from the howstuffworks site:
Quantum computers aren't limited to two states; they encode information as quantum bits, or qubits. A qubit can be a 1 or a 0, or it can exist in a superposition that is simultaneously both 1 and 0 or somewhere in between.
Now this is where I yawn and crawl back to my hibernation state ;-)
I think this proves how difficult it is for humans to understand something new if you've been "programmed" with older information. This might be why it is so difficult for us to solve these "hard" problems - we are too set in trying to solve problems the traditional way?
That is why it is called a breakthrough, isn't it? ;-)
Speaking of approaching problems in a nonstandard way. I gave your accounting problem some more thought and wondered whether you tried to use a combination of the genetic algorithm and the brute force way? I mean try and learn the program to a point where it can sort of guess and then from there on try and do a brute force for the parts that are not solved by updating the results you got from the GP. Not sure if this will work or even if it makes sense ;-)
Speaking of approaching problems in a nonstandard way. I gave your accounting problem some more thought and wondered whether you tried to use a combination of the genetic algorithm and the brute force way? I mean try and learn the program to a point where it can sort of guess and then from there on try and do a brute force for the parts that are not solved by updating the results you got from the GP. Not sure if this will work or even if it makes sense ;-)
I had the same thing in mind with the genetic algorithm.
It is unfortunately difficult for me to point the algorithm in the correct direction in the search space. In genetic algorithms, each "node" has a fitness function, which should represent how close this node is to the "answer". By creating new generations, you point the nodes in the correct direction. The idea is that by hopefully changing just one or two attributes of a node that it should result in a better answer.
The problem I've seen with this accounting example, is that even if you take the worst node and change just one attribute, it all of a sudden becomes the best node. The same for the best node - it easily becomes the worst node.
This result in the nodes jumping around (almost randomly) in the search space. So you are not using the power of genetic algorithms. You might as well just search randomly!
So it is difficult for me to say at any stage that I'm now "close" to the answer, so let's try brute force from now on..
Note that this is just my experience with genetic algorithms specifically for this problem. I'm not an expert at all!
It is unfortunately difficult for me to point the algorithm in the correct direction in the search space. In genetic algorithms, each "node" has a fitness function, which should represent how close this node is to the "answer". By creating new generations, you point the nodes in the correct direction. The idea is that by hopefully changing just one or two attributes of a node that it should result in a better answer.
The problem I've seen with this accounting example, is that even if you take the worst node and change just one attribute, it all of a sudden becomes the best node. The same for the best node - it easily becomes the worst node.
This result in the nodes jumping around (almost randomly) in the search space. So you are not using the power of genetic algorithms. You might as well just search randomly!
So it is difficult for me to say at any stage that I'm now "close" to the answer, so let's try brute force from now on..
Note that this is just my experience with genetic algorithms specifically for this problem. I'm not an expert at all!
Ok, smartass.. I won't be recalculating that ;-)
Even though you might be wrong, bonus points for double-checking my calculations!
The point is just that quite quickly, a brute force way is not viable anymore.
Even though you might be wrong, bonus points for double-checking my calculations!
The point is just that quite quickly, a brute force way is not viable anymore.
That's definitely interesting.. the part that turns my brain into a spin is this:
"made quantum computers"..
I mentioned this before, but the fact is it seems like we need something like quantum computers to help solve these kinds of problems. What about solving these kind of problems on existing computer architectures?
Post a Comment
"made quantum computers"..
I mentioned this before, but the fact is it seems like we need something like quantum computers to help solve these kinds of problems. What about solving these kind of problems on existing computer architectures?
<< Home
