Method for classification of the computational problems on the basis of the multifractal division of the complexity classes
Abstract:
This paper proposes the method of the multifractal division of the computational complexity classes, which is formalized by introducing the special equivalence relations on these classes. Exposing the self-similarity properties of the complexity classes structure, this method allows performing the accurate classification of the problems and demonstrates the capability of adaptation to the new advances in the computational complexity theory.
References:
A. Potebnia and S. Pogorilyy, "Investigation of transformations and landscapes for combinatorial optimization problems", 2016 13th International Conference on Modern Problems of Radio Engineering Telecommunications and Computer Science (TCSET), pp. 510-514, 23–26 Feb. 2016
View in Google ScholarM. Senechal, Quasicrystals and Geometry, New York:Cambridge University Press, 1996.
View in Google ScholarA. Potebnia and S. Pogorilyy, "Fast output-sensitive approach for minimum convex hulls formation", Recent Advances in Computational Optimization: Results of the Workshop on Computational Optimization WCO 2015, vol. 655, pp. 1-20, 2016.
View in Google ScholarR. Ladner, "The circuit value problem is log space complete for P", SIGACT News, vol. 7, pp. 18-20, 1975.
View in Google Scholar
