In computer science, the complexity of a problem, say sorting N numbers, is measured by the number of basic operators, e.g. O(N log N).
  In computer vision,  the complexity measure includes two aspects: the computational complexity and the problem complexity. The latter 
  includes error rates and error bounds:

      Unlike the sorting problem, we cannot solve a problem exactly and not  100% correctly.  For example, it is impossible to design
  an edge detector or a face detector which is 100% correct.  Therefore, various bounds are needed to measure the fundamental
  limits.  For example, there are a three traditional bounds.
                         
                         a). The Cramer-Rao bound.        To learn a model with parameters, given finite data the parameter can be learned
                                                                                only to a certain precision. This is related to the Fisher's information which measures
                                                                                how flat the likelihood is.
                         b). Chernoff/Bhatta information.  For two classes whose probability densities overlap, the fundamental limit of
                                                                                 distinguishing the two classes is the measured by the Chernoff information which
                                                                                 is a distance measure of the two densities. When the two densities are Gaussian
                                                                                 with equal variance. This reduces to the signal-to-noise ratio (SNR).
                         c). Channel Capacity and mutual information. From certain features and evidence x, the ability for discriminating 
                                                                                other variables y is limited by the mutual information between x and y.
 
                        However, real applications are far more difficult to measure than the two simple cases. 
                 
                For example, the figures below show three typical regimes: Detecting a stop sign is easy, detecting an animal adapted to its
           environment is much difficult, and detecting the dalmation dog in the snow scene is almost impossible. 

 
          The order parameter theory was developed and linked with the minimax entropy learning. It can do two things:

   1). The error probability for discrimination is an exponential number     exp(-nK) with n being  the number of observations and
            K is a rate.  When K is large, the task is easy. When K is nearly zero, then it is very hard. When K is negative, then the
            task is impossible.  The figures below show three typical situations for detecting a target road (curve) in clutter.

    2).  The order parameter than is related to the minimax entropy learning: for large K and easy task, we can learn a simple model
which will be enough. For small K, the models for the patterns will have to be more sophisticated.

 [1]    Y. N. Wu,  S. C. Zhu, and X. W. Liu,  "Equivalence of Julesz Ensemble and FRAME models", 
               International Journal of Computer Vision, 38(3), 247-265, July, 2000. 
 
 [2]    A.L. Yuille and J.M. Coughlan,   ``Fundamental Limits of Bayesian Inference: Order Parameters and Phase Transitions for
                 Road Tracking'' .  IEEE Trans. on Pattern Analysis and Machine Intelligence PAMI. Vol. 22. No. 2. February. 2000.

 [3]  A. L. Yuille, J. M. Coughlan, Y. N. Wu, and S. C. Zhu,   "Order Parameter for Detecting Target Curves in Images: How does
              High Level  Knowledge Helps?"     International Journal of Computer Vision, vol. 41, No. 1/2, pp.9-33, January, 2001. 
 
 [4]  S. Kinishi, J. M. Coughlan, A. L. Yuille, and S. C. Zhu,  "Fundamental Bounds on Edge Detection: an Information Theoretic 
             Evaluation of Different Edge Cues",  IEEE Trans. on Pattern Analysis and Machine Intelligence, vol.25, no.1, January, 2003.
  
 [5]  S. Zhu, A.D. Lanterman, and M.I. Miller, "Clutter modeling and Performance analysis in Automatic Target recognition",
           Workshop on Detection and Classification of Difficult Targets, Redstone Arsenal, Alabama, 1998