Equivalence of Complexity Classes via Finite Automata Derivatives

Authors

Keywords:

subset construction, regular expression, P versus NP, derivatives

Abstract

In this article practical, experimental and theoretical results of the conducted research are presented, these results refer to the main question in complexity theory like the “P versus NP” theorem, first proposed by Stephen Cook in his seminal paper, we give concise question of the equivalence of these classes from the state of conversion algorithm of non-deterministic finite automata (NFA) to deterministic finite automata (DFA), we do it by considering the canonical regular expression form presented by Schneider Klaus and do the derivative processing from the Berry-Sethi algorithm, the result gives P-complete algorithm along the canonical form of regular expressions when applying subset construction for specific regular expressions or NFA, DFA in this case remains applicable even for Turing tape machines, however, due to the past statement of the “P versus NP” theorem given by author in previous work this leads to the conclusion of the equivalence of complexity classes like P and NP as in canonical form the subset construction produces exponential growth of the number of states of DFA

Downloads

Download data is not yet available.

Author Biography

Mirzakhmet Syzdykov, n/a

Born 11/09/84. 2006-2009, aspirant at Institute of Problems in Informatics and Control

Downloads

Published

2022-12-29

How to Cite

Syzdykov, M. (2022). Equivalence of Complexity Classes via Finite Automata Derivatives. ADVANCED TECHNOLOGIES AND COMPUTER SCIENCE, 1(4), 9–14. Retrieved from https://atcs.iict.kz/index.php/atcs/article/view/105

Issue

Section

Artificial intelligence technologies

Most read articles by the same author(s)