ON EXPERIMENTAL PROOF OF P VERSUS NPTHEOREM
Syzdykov M.B. Kardeis Y.L.
30 September 2025al-Farabi Kazakh State National University
KazNU Bulletin. Mathematics, Mechanics, Computer Science Series
2025#127Issue 366 - 95 pp.
We propose a simple and intuitive algorithm for solving md-DFA problem using algorithm concepts within extended operators, our approach shows quadratic polynomial time and hence proves the equivalence between polynomial and non-polynomial classes, we have also shown that minimal non-emptiness of automata problem can be solved in polynomial time with help of modified subset construction, rather that building a product automaton, which lead to factorial size of the memory and time, in this work we also have used many non-tractable existing examples and computed them in polynomial time, which guarantees that our algorithm solves NP-complete problem in almost linear polynomial time, we have also avoided the problem of product automata by an algorithmic approach, we are also giving the starting ground for the proof of back-reference problem which was discussed before, notion to the globally local increment is also given as the main argument towards the resolution of P versus NPtheorem, which coincides with the finitarity term in general mathematics.
complexity , experimental , P versus NP , proof , theorem
Text of the article Перейти на текст статьи
Satbayev University, Almaty, Kazakhstan
Rheinland-Pfälzische Technische Universität Kaiserslautern-Landau, Pfalz, Germany
Satbayev University
Rheinland-Pfälzische Technische Universität Kaiserslautern-Landau
10 лет помогаем публиковать статьи Международный издатель
Книга Публикация научной статьи Волощук 2026 Book Publication of a scientific article 2026