Formation of the multifractal hypergraph structure reflecting the self-similarity properties of the computational complexity classes
Abstract:
In the context of classifying the graph structures from the viewpoint of their self-similarity, this paper introduces the original concepts of the fractal and multifractal hypergraphs. The key idea underlying their definitions consists in the iterative procedure of generating the hyperedges applied to the specified initiator structure. The paper discusses the main properties of such hypergraphs and presents the simplified examples of their instances. Against this background, the investigation proposes the approach for representing the self-similarity properties of the computational complexity classes in terms of the multifractal hypergraph structure.
References:
A. Potebnia, "Method for classification of the computational problems on the basis of the multifractal division of the complexity classes", Problems of Infocommunications. Science and Technology (PIC S&T) Third International Scientific-Practical Conference on, pp. 1-4, 2016.
View in Google ScholarV. Perepelitsa, I. Sergienko and A. Kochkarov, "Recognition of fractal graphs", Cybernetics and Systems Analysis, vol. 35, no. 4, pp. 572-585, 1999.
View in Google ScholarC. Papadimitriou, Computational Complexity, Addison Wesley, 1994.
View in Google ScholarV. Arvind, J. Köbler, S. Kuhnert, G. Rattan and Y. Vasudev, "On the Isomorphism Problem for Decision Trees and Decision Lists", Theoretical Computer Science, vol. 590, pp. 38-54, 2015.
View in Google Scholar
