From InterSciWiki

[edit] Singularity Theory and Complex Systems

One example of a complex system is the game theoretic interaction between economic agents. The most generic example of this is the classic n player game with utility-maximizing agents. I consider it a compelx system because it contains:

• A large number of parts
• The parts are interdependent
• The parts are adaptive

Essentially the interdependence of a large number of adaptive agents is what I consider a classic example of social complexity. So it is of interest to be able to characterize the generic properties of equilibrium solution sets for an n player system. A paper by Amer Aladhadh and Donald Saari provides the generic properties of the solution sets provided by solution concepts.

The results show that equilibria such as Nash amongst many actors are generically isolated points. This means that with changing the utility functions ever so slightly, there is a neighborhood around the old solution small enough not contain the old one.

More illuminating is the result that many types of constrained games generically have no Nash equilibria. This means that one can find some examples where they exist, but if you perturb the assumed functional assumptions ever so slightly, these equilibria disappear.

This idea is where the number of actors will constrain the solution space further until it generically disappear. This method then offers an analytical method to classifying the complexity of problems by characterizing the dimension of the solution space.

The results give the dimension of both interior solution and corner solutions underlining that the increased complexity of the porblem may reduce the dimension of the space of interior equilibria or restrict the solution space to corner solutions.

[edit] P versus NP

One particular problem with the 3 SAT is filtering out redundant linear constraints imposed by the number of logical conditions in the problem. I suspect that the reduction of the these equations into matrices, then using the balancedness condition used in cooperative game theory to weed out redundant linear constraints, may solve that issue. If there was a singularity theory that can handle the three SAT problem, one can show that the dimensions of the solution space are related to search time and that this increased compelxity is the difference between p versus np. At the very least, singularity theory will give you the genenric properties of solutions and thereofore solution search time. I am responsible for all errors in the logic above, because it is mine alone, but if you wanted a great introduction to the 3 SAT and P versus NP, please see Chris Moore's excellent lecture on the institute for complexity 2008 Summer School.