For those who are interested in the current state of the potential P ≠ NP proof, Michael Nielsen is collecting various sources on a wiki. This includes the current version of the paper, a summary of the proof as well as arguments regarding flaws in the paper. Anyway, for more click here or on the image above.
I am going to bump this post to front of the blog one last time. We have now completed the full four week class here at the ICPSR Summer Program in Quantitative Methods. In this course, I (together with my colleagues) highlight the methods of complex systems as well as several environments designed to explore the field. These include Netlogo (agent based models and network models), Vensim (system dynamics / ecological modeling) and Pajek (empirical network analysis). In the final week, we cover a variety of advanced topics:
Although, we do not work with more advanced languages within the course, those who need to conduct complex analysis are directed to alternatives such as R, Python, Java, etc.
Anyway, the slides are designed to be fully self-contained and thus allow for individually paced study of the relevant material. If you work through the slides carefully you should be able to learn the software as well as many of the core principles associated with the science of complex systems. The material should be available online indefinitely. If you have questions, feel free to email me.
This week in the Proceedings of the National Academy of Sciences comes a very important article entitled Hypothesis-driven structural connectivity analysis supports network over hierarchical model of brain architecture by Richard H. Thompson and Larry W. Swanson of the University of Southern California. Above is the BBC coverage regarding the paper. Here is the press release from USC. Here is the story from Science Daily. This article is worth the read!
UPDATED VERSION HAS BEEN PUBLISHED TO THE WEB (August 9, 2010) [Click Here!]
After sending his paper to several leading researchers in the field and acquiring support, Vinay Deolalikar from HP Labs has recently published P ≠ NP to the web. While it has yet to be externally verified by folks such as the Clay Mathematics Institute, it looks very promising. Indeed, this very well represent a Millennium Prize for Mr. Deolalikar. For those interested in additional information, check out Greg Baker’s blog (which broke the story). Very exciting!
For initial thoughts on the matter by Dick Lipton, see the latest post on the blog Gödel’s Lost Letter and P=NP.
To read more about the history and importance of P vs. NP, please consult these sources:
Diversity is one the major topics of interest here at Michigan Center for the Study of Complex Systems. This includes diversity as experienced in physical as well as in social systems. On this topic, here is a lecture that one of my dissertation advisors, Scott Page gave earlier this year at the Darden School of Business at Virginia. This lecture is related to his book about the power of diversity entitled: The Difference: How The Power of Diversity Creates Better Groups, Firms, Schools, and Societies. Although I realize it is roughly a 90 minute talk, I believe that you will find that it is well worth the time!
“At TEDGlobal 2010, author Matt Ridley shows how, throughout history, the engine of human progress has been the meeting and mating of ideas to make new ideas. It’s not important how clever individuals are, he says; what really matters is how smart the collective brain is.”
This summer, I am teaching the Introduction to Computing for Complex Systems course at the ICPSR 2010 Program in Quantitative Methods. On the first day of class, I previously blogged about the course and thus if you are interested in additional details — feel free to consult the prior post.
For those interested in an introductory course that does not assume significant prior preparation, I did want to put up another post highlighting that all of course material (to date) is now freely available online. This includes course slides, model examples and assignments.
In this introductory course, I highlight several environments designed to explore the field of complex systems. These include Netlogo (agent based models and network models), Vensim (system dynamics / ecological modeling) and Pajek (empirical network analysis). Although, we do not work with more advanced languages within the course, those who need to conduct complex analysis are directed to alternatives such as R, Python, Java.
In the course slides, I offer a history of the science of complex systems and walk step-by-step through the process of model development and implementation. The slides and associated materials are designed to be a complete self-teaching environment where an individual who follows along carefully should be able to bring him or herself up to speed. More material will be added over the balance of the four-week session. So, please check back for more … including slides from our guest speakers!
Understanding the sources of complexity in legal systems is a matter long considered by legal commentators. In tackling the question, scholars have applied various approaches including descriptive, theoretical and, in some cases, empirical analysis. The list is long but would certainly include work such as Long & Swingen (1987), Schuck (1992), White (1992), Kaplow (1995), Epstein (1997), Kades (1997), Wright (2000) and Holz (2007). Notwithstanding the significant contributions made by these and other scholars, we argue that an extensive empirical inquiry into the complexity of the law still remains to be undertaken.
While certainly just a slice of the broader legal universe, the United States Code represents a substantively important body of law familiar to both legal scholars and laypersons. In published form, the Code spans many volumes. Those volumes feature hundreds of thousands of provisions and tens of millions of words. The United States Code is obviously complicated, however, measuring its size and complexity has proven be non-trivial.
In our paper entitled, A Mathematical Approach to the Study of the United States Code we hope to contribute to the effort by formalizing the United States Code as a mathematical object with a hierarchical structure, a citation network and an associated text function that projects language onto specific vertices.
In the visualization above, Figure (a) is the full United States Code visualized to the section level. In other words, each ring is a layer of a hierarchical tree that halts at the section level. Of course, many sections feature a variety of nested sub-sections, etc. For example, the well known 26 U.S.C. 501(c)(3) is only shown above at the depth of Section 501. If we added all of these layers there would simply be additional rings. For those interested in the visualization of specific Titles of the United States Code … we have previously created fully zoomable visualizations of Title 17 (Copyright), Title 11 (Bankruptcy), Title 26 (Tax) [at section depth], Title 26 (Tax) [Capital Gains & Losses] as well as specific pieces of legislation such as the original Health Care Bill – HR 3962.
In the visualization above, Figure (b) combines this hierarchical structure together with a citation network. We have previously visualized the United States Code citation network and have a working paper entitled Properties of the United States Code Citation Network. Figure (b) is thus a realization of the full United States Code through the section level.
With this representation in place, it is possible to measure the size of the Code using its various structural features such as vertices V and its edges E. It is possible to measure the full Code at various time snapshots and consider whether the Code is growing or shrinking. Using a limited window of data, we observe growth not only in the size of the code but also its network of dependancies (i.e. its citation network).
Of course, growth in the size United States Code alone is not necessarily analogous to an increase in complexity. Indeed, while we believe in general the size of the code tends to contribute to “complexity,” some additional measures are needed. Thus, our paper features structural measurements such as number of sections, section sizes, etc.
In addition, we apply the well known Shannon Entropy measure (borrowed from Information Theory) to evaluate the “complexity” of the message passing / language contained therein. Shannon Entropy has a long intellectual history and has been used as a measure of complexity by many scholars. Here is the formula for Shannon entropy:
For those interested in reviewing the full paper, it is forthcoming in Physica A: Statistical Mechanics and its Applications. For those not familiar, Physica A is a journal published by Elsevier and is a popular outlet for Econophysics and Quantitative Finance. A current draft of the paper is available on the SSRN and the physics arXiv
We are currently working on a follow up paper that is longer, more detailed and designed for a general audience. Even if you have little or no interest in the analysis of the United States Code, we hope principles such as entropy, structure, etc. will prove useful in the measurement of other classes of legal documents including contracts, treaties, administrative regulations, etc.
This week’s “economic focus” in the Economist highlights Agent Based Modeling as an alternative to traditional economic models and methods. As I am currently teaching Agent Based approaches to modeling as part of the ICPSR Introduction to Computing for Complex Systems, I am quite pleased to see this coverage. Indeed, the timing could not be better and I plan to highlight this article in the course!
Here are some highlights from the article: “… Agent-based modelling does not assume that the economy can achieve a settled equilibrium. No order or design is imposed on the economy from the top down. Unlike many models, ABMs are not populated with “representative agents”: identical traders, firms or households whose individual behaviour mirrors the economy as a whole. Rather, an ABM uses a bottom-up approach which assigns particular behavioural rules to each agent. For example, some may believe that prices reflect fundamentals whereas others may rely on empirical observations of past price trends. Crucially, agents’ behaviour may be determined (and altered) by direct interactions between them, whereas in conventional models interaction happens only indirectly through pricing. This feature of ABMs enables, for example, the copycat behaviour that leads to “herding” among investors. The agents may learn from experience or switch their strategies according to majority opinion. They can aggregate into institutional structures such as banks and firms …” For those who are interested, I have made similar points in the post “Complex Models for Dynamic Time Evolving Landscapes –or– Herb Gintis Offers a Strong Rebuke of “Meltdown.“
