Computational Complexity and Popsicles

Wicked problems“[1][2], such as climate change, poverty, and geopolitical instability, tend to be ill-defined, multifaceted, and complex such that solving one aspect of the problem may create new, worse problems.  Thus, trying to engineer solutions to such problems is exacerbated by our inability to measure overall improvement.  For example, we may observe economic improvements in a locale where we have implemented a poverty mitigation strategy, only to discover later that we have inadvertently introduced health issues that ultimately result in even worse financial burdens related to the consequent healthcare needs.  And there may be other deleterious side-effects that are difficult to measure or that we fail to attribute to our implemented solution.  So what can be done?

Given our interest in applying human-based computational (HC) systems to solving these problems, we might gain insight from computational complexity theory.  This theoretical branch of computer science seeks to classify computational problems based on how difficult they are to solve.  It answers questions like, “How long would it take (at best and worst) to find the shortest path that visits each of these eight U.S. cities exactly once?”  It turns out that problems such as this one, canonically referred to as the “Traveling Salesman Problem“, are considered computationally intractable.   Indeed, for the Traveling Salesman Problem, the processing time for the best known solution increases by a factor of n22n.  In practical terms, a computer that takes one minute to find the shortest path between eight cities would take more than 11 years to find the shortest path between thirty cities.  But here’s the rub: there is no way to verify the solution other than to check it against all other possible paths, which is tantamount to recomputing the solution.

Just as the Traveling Salesman Problem is intractable for machines, wicked problems are intractable for humans.  The problem complexity for wicked problems is very high, but so is evaluating their solutions.  For such problems, assessing improvement broadly can be just as vexing as engineering a solution in the first place.  However, there is another version of the Traveling Salesman Problem for which solution verification is more tractable.  Instead of asking for an optimal path, this version asks a slightly different question: “Is there a path shorter than x that visits each of these cities once?”  This version of the problem does not materially change its difficulty classification, but it does make the solution much easier to evaluate.    Indeed, verifying the solution involves simply adding up the distances along the provided path and comparing the result to the mileage budget (x).  In this case, if my budget of allowed miles is 300, then we just need to verify that the provided itinerary is within-budget – that is, ensure that the generated path that visits each city exactly once is less than 300 miles.  In computational complexity theory, intractable problems for which solution verification can be performed quickly (i.e., in polynomial time) are considered “NP-complete”.  Another example of a problem that is NP-complete is prime factorization.   Today’s computers take a very long time to factor large numbers, the latency of which makes common encryption methods secure.  However, once a number has been decomposed into its prime factors, it is easy to verify the solution by simply multiplying the factors together and comparing the result to the original number.

Perhaps a first and more attainable step to solving wicked problems would be to reframe the problem in a manner analogous to the modified version of the Traveling Salesman Problem described above.  Instead of seeking an optimal solution to a wicked societal problem, perhaps we should seek a solution that simply meets the yes/no criterion of “would this be an improvement over what we have now”.  But how do we broadly measure such improvement?   Could human computation be used to enable tractable solution verification for wicked problems?  Enter the “Popsicle Index”.  Catherine Austin Fitts has proposed a very simple metric for a community’s well-being based on the percent of community members who “believe that a child can leave their home, go to the nearest place to buy a popsicle or other snack, and return home alone safely”[3].

This index is remarkable for several reasons.  First, it cleverly captures a multitude of individual effects, confluent effects, and n-order effects.  For example, the child’s safety could be related to traffic risks, a bad element hanging around the store, or even the perceived risk of chemicals in the purchased snack.  I would go so far as to call it a “wicked metric” because trying to understand the full set of factors and interactions that govern the Popsicle Index might itself constitute a wicked problem.  Second, the Popsicle Index is an HC approach to solution assessment that involves crowdsourcing and aggregating subjective human assessments.  Though such assessments might be of sufficient complexity to be considered intractable for machines, due to differences in computational strategies between humans and machines, such problems are often strong candidates for HC solutions[4]. Third, and perhaps most germane to this discussion the Popsicle Index, as a straight-forward window into community well-being, could facilitate solutions to wicked societal problems by reclassifying those problems from intractable to NP-complete.  Just as with the NP-complete version of the Traveling Salesman Problem, we may not have a quick way to know if we have an optimal solution, but we might at least have a sense of whether we are making things better or worse.  Indeed, the prospect of such comprehensive measures of improvement may bring us one step closer to addressing societal challenges.

What other “wicked metrics” might we explore?

– Pietro Michelucci

Acknowledgments:  I am grateful to Christina Engelbart for bringing the Popsicle Index to my attention and to Jordan Crouser for corrections and feedback that materially improved this article.


[1] H. Rittel and M. Webber, “Dilemmas in a General Theory of Planning,” Policy Sci., vol. 4, pp. 155–169, 1973.

[2] “Wicked problem,” Wikipedia, the free encyclopedia. 08-Jan-2015

[3] C. A. Fitts, “The Popsicle Index – who makes it go up? who makes it go down?” Solari Blog.

[4] R. J. Crouser, B. Hescott, and R. Chang, “Toward Complexity Measures for Systems Involving Humans,” Human Computation, vol. 1, no. 1, Sep. 2014.