Article number 1
Published in RGT on November 18, 2020

Method for classification of the computational problems on the basis of the multifractal division of the complexity classes

Keywords:
computational problem, P and NP classes, reduction, equivalence relation, multifractal

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:

1. 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 Scholar

2. M. Senechal, Quasicrystals and Geometry, New York:Cambridge University Press, 1996.

View in Google Scholar

3. A. 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 Scholar

4. R. Ladner, "The circuit value problem is log space complete for P", SIGACT News, vol. 7, pp. 18-20, 1975.

View in Google Scholar

Full Text:

Supplementary Files:

  • Presentation on the article
2020

Abstract viewed:
89

PDF downloaded:
38

Presentation on the article downloaded:
0
How to Cite:
IEEE Citation Style
▾
  • IEEE Citation Style
  • ACM Citation Style
  • APA Citation Style
  • Harvard Citation Style
  • MLA Citation Style
  • Turabian Citation Style
  • Chicago Citation Style
A. Potebnia, “Method for classification of the computational problems on the basis of the multifractal division of the complexity classes,” 3rd International Scientific-Practical Conference on Problems of Infocommunications Science and Technology, pp. 1 – 4, 2016. DOI: 10.​1109/INFOCOMMST.​2016.​7905318. Open-access version available at https://purl.org/artempotebnia/1
Section:
Original Scientific Articles in Graph Theory
Universal Resource Name:
https:/
/
purl.
org/
artempotebnia/
1
Reading Tools:
Method for classification of the computational problems on the basis of the multifractal division of the complexity classes

Authored by: Artem Potebnia
ORCID: https://orcid.org/0000-0002-8162-5613

Keywords: computational problem, P and NP classes, reduction, equivalence relation, multifractal

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.