A Probabilistic Understanding of Computational Complexity, a Singularity Theory Approach

This note develops a probabilistic understanding of computational complexity. Using singularity theory, the paper shows the generic dimension of a solution in search space. Then, the complexity of a problem is defined in terms of expected time for a nondeterministic search to reach the solution space within the search space. The search space size and dimension vary with the problem while dimension of the solution space depends on the number of binding restrictions for a solution. These generic properties of the solution space can be obtained using singularity theory. As a motivational example, this paper uses singularity theory to characterize the generic properties of cut the cake problem and the dimensionality of its solutions subspace under different solution conditions and restrictions. Using the generic size of the solution space compared to the domain, the paper builds complexity in terms of number of iterations to the first solution. This measure theoretic definition makes more intuitive the problem of computational complexity. The paper shows that under the measure theoretic definition cutting the cake problem goes from P to NP to unsolvable depending on the solution criteria.