Scientists Prove Toxic Assets are Impossible to Regulate
1–10 of 24 posts
Re: Scientists Prove Toxic Assets are Impossible to Regulate
#2Re: Scientists Prove Toxic Assets are Impossible to Regulate
#3A fairly good summary, though I'm not certain someone who hasn't studied computability is going to get it. The "See Also" amichail posted is good.
Re: Scientists Prove Toxic Assets are Impossible to Regulate
#4The question now is whether this information will have any effect in Washington. My bet is that it will not.
Re: Scientists Prove Toxic Assets are Impossible to Regulate
#5hold the phone, just because a problem is NP complete does not mean that it is computationally intractable. most algorithms in the real world are NP complete, but people still try to solve them.
just because there's no way to prove which CDOs have been tampered with doesn't mean that you can't figure it out. there are local search algorithms that may be able to give you a pretty good answer, even if you don't know for sure. there's some extra risk in CDOs because of this, fine, but it doesn't mean that the market would be locked up, or that no one would have any clue if there was misconduct.
regulators also have extra tools to detect fraud. maybe the buyer can't tell, but if the buyer suspects, and the regulator can check the seller's internal records, examine their processes, and in general, investigate whether the seller did any tampering.
Re: Scientists Prove Toxic Assets are Impossible to Regulate
#6hold the phone, just because a problem is NP complete does not mean that it is computationally intractable. most algorithms in the real world are NP complete, but people still try to solve them. just because there's no way to prove which CDOs have been tampered with doesn't mean that you can't figure it out. there are local search algorithms that may be able to give you a pretty good answer, even if you don't know fo…
As much as I love dailykos at times, considering that on top of the factual inaccuracy you point out, the non-watered down non-hysteric version [1] was pretty popular here a little bit ago, I think this article deserves some [dead]-ing.
Re: Scientists Prove Toxic Assets are Impossible to Regulate
#7I only read the abstract and the Daily Kos summary, and am not a complexity theorist, but I have to say this seems a little facetious. Sure the valuation problem might be np-complete, so technically you can't "solve" it. This has a nice ring and I'm sure lots of members of congress are going to hoist this paper aloft in hearings while they're busy chewing out the CEO of Lehman.
But approximation techniques are being used all the time to obtain near-optimal solutions to NP-hard problems. If you can obtain a valuation for a complex bundle of derivatives that's within 10% of the true value, then it seems silly to claim that they whole practice should be tossed out the window. This is like saying salesmen should no longer be able to travel because we cannot solve the traveling salesman problem.
Re: Scientists Prove Toxic Assets are Impossible to Regulate
#8It's also impossible for a traveling salesman to find the best route between cities, but that doesn't mean that salesmen don't travel. Approximations are often Good Enough, and there are a variety of polynomial algorithms that produce Good Enough solutions to NP problems.
Everything in the real world is impossible, but we can try and get good results anyway.
Re: Scientists Prove Toxic Assets are Impossible to Regulate
#9It's also impossible for a traveling salesman to find the best route between cities, but that doesn't mean that salesmen don't travel. Approximations are often Good Enough, and there are a variety of polynomial algorithms that produce Good Enough solutions to NP problems. Everything in the real world is impossible, but we can try and get good results anyway.
[deleted]
Re: Scientists Prove Toxic Assets are Impossible to Regulate
#10hold the phone, just because a problem is NP complete does not mean that it is computationally intractable. most algorithms in the real world are NP complete, but people still try to solve them. just because there's no way to prove which CDOs have been tampered with doesn't mean that you can't figure it out. there are local search algorithms that may be able to give you a pretty good answer, even if you don't know fo…
It's probably even worse than that, in that one probability isn't evidence of cheating, whether you have found the optimal dense subgraphs or not.
The biggest I take from this (apart from it being an interesting analysis in itself) is that if there is an assumption of randomness in creation of CDO's that should be verified at creation.