Figure 1. Nested set of solution spaces for different degrees of problem hardness.
Figure 2. Is this a wicked problem? Is this how it should be set up?
1) ill-defined problem space: In a recent workshop (HTDE 2012), I discussed the attributes of "hard-to-define" problems. While not all hard-to-define problems are wicked, wicked problems do not feature a closed or even finite set of possible solutions. Whether they can truly be treated using an algorithmic framework is not clear.
2) all solutions are heuristic: due to the limitations of the first feature, any given wicked problem has no exact solution. The problem space will be characterized by many different solutions, likely context-dependent (the word "contingent"  can also be used).
3) there is no "stopping rule" for wicked problems. In conventional computing, the is an end point to a simulation of program that can be defined either deterministically (program-dependent) or stochastically (a Turing machine). With wicked problems, there is no natural stopping point, as the problem has no natural end-point .
4) so-called "messes"  define interactions between subdomains of the problem. In this case, a problem's subdomains form a dense, fully-connected network which cannot be decomposed to reveal clear causal or associative relationships. Instead of being merely massively parallel, such problems are at least massively interactive and are often exhibit parallelism as well. Furthermore, such messes often transcend formal system-level boundaries, and from a phenomenological standpoint implicate several loosely-related systems.
Figure 3. Two first-pass approximations at wicked problems? LEFT: M.C. Escher's Mobius Strip, RIGHT: SimCity.
How is this perspective useful for computing and solving complex scientific problems? Well, it is not so much useful as it is a challenge. There is much work to be done here. So what a challenge it is !
 Papadimitriou, G.H. Computational Complexity. Addison-Wesley, Boston (1994).
 Brown, V.A., Harris, J.A., and Russell, J.Y. Tackling Wicked Problems: Through the Transdisciplinary Imagination. Earthscan, London (2010).
 According to Wikipedia, C. West Churchman introduced the term in 1967, which was expanded upon in the following paper:
Rittel, H.W.J. and Webber, M.M. Dilemmas in a General Theory of Planning. Policy Sciences, 4, 155-169 (1973).
 Mandelbrot, B. and Hudson, R.L. The (mis)Behavior of Markets: a fractal view of risk, ruin, and reward. Basic Books, New York (2004).
Lazarus, R.J. Super Wicked Problems and Climate Change: Restraining the Present to Liberate the Future. Cornell Law Review, 94(5), Georgetown Public Law Research No. 1302623 (2009).
However, the things that define a wicked problem apply to a much larger class of problems. Formal methods are needed.
 Levin, K., Cashore, B., Bernstein, S., and Auld, G. Playing it forward: Path dependency, progressive incrementalism, and the "Super Wicked" problem of global climate change. IOP Conference Series: Earth and Environmental Science, 50(6) (2009).
 an example might be cultural or biological evolution, which do not "end" until some major catastrophe wipes out the entire system. In these examples, it is interesting to note that you can observe an artificially-determined endpoint, but it does not always reveal a definitive solution (e.g. natural selection and the evolution of "maximally adaptive" traits).
 According to Wikipedia, this term was originally coined by Russell Ackoff. Please see the following reference:
Ackoff, R. Systems, Messes, and Interactive Planning. In "Redesigning the Future". Wiley, New York (1974).
 I have no prize to offer for anyone who proposes reasonable-sounding solutions or formal methods. It's just a call-to-arms.