## Data Structures and Algorithms   ## A New Algebraic Approach to the Graph Isomorphism and Clique Problems

Authors: Roman Galay

As it follows from Gödel's incompleteness theorems, any consistent formal system of axioms and rules of inference should imply a true unprovable statement. Actually this fundamental principle can be efficiently applicable in Computational Mathematics and Complexity Theory concerning the computational complexity of problems from the class NP, particularly and especially the NP-complete ones. While there is a wide set of algorithms for these problems that we call heuristic, the correctness or/and complexity of each concrete algorithm (or the probability of its correct and polynomial-time work) on a class of instances is often too difficult to determine, although we may also assume the existence of a variety of algorithms for NP-complete problems that are both correct and polynomial-time on all the instances from a given class (where the given problem remains NP-complete), but whose correctness or/and polynomial-time complexity on the class is impossible to prove as an example for Gödel's theorems. However, supposedly such algorithms should possess a certain complicatedness of processing the input data and treat it in a certain algebraically “entangled” manner. The same algorithmic analysis in fact concerns all the other significant problems and subclasses of NP, such as the graph isomorphism problem and its associated complexity class GI. The following short article offers a couple of algebraically entangled polynomial-time algorithms for the graph isomorphism and clique problems whose correctness is yet to be determined either empirically or through attempting to find proofs. Besides, the paper contains a description of an equation system for elements of a set of groups (which can also be interpreted as an algebraic equation system) that can be polynomial-time reduced to a graph isomorphism problem and, in the same time, is a non-linear extension of a system of modular linear equations where each equation has its own modulus (hence implying the question whether it’s NP-complete).

### Submission history

[v1] 2019-03-13 16:20:16
[v2] 2019-03-20 11:58:28
[v3] 2019-04-16 04:33:43
[v4] 2019-04-25 16:14:48
[v5] 2019-05-03 16:11:44