Glyph Algorithm - SPAZKEY LLC

GLYPH ALGORITHM

Spazkey LLC

Richard Everhart, Co-Founder and CTO

11/9/2015

Summary

The Glyph Algorithm is a solution to a case of the Boolean Satisfiability problem (k-SAT) and is therefore capable of determining satisfiable interpretations to any given Boolean expression in conjunctive normal form. Unlike tactics utilized by what are presently considered to be the most efficient algorithms for solving SAT, Glyph does not rely on collision detection and backtracking operations as a means of decreasing computational complexity. Rather, the glyph algorithm solves SAT by reducing a given Boolean expression to a new format, known as Glyph form, such that it is absent of the issue normal SAT solvers have in accounting for variable repetition. In doing so, both what operators represent and how these representations are affected by variable repetition are able to be acknowledged with minimal computational effort. This results in an algorithm which is capable of solving k-SAT with a drastically heightened degree of efficiency in comparison to currently available high performing SAT solvers.

Importance

Because Glyph is able to efficiently satisfy Boolean expressions, and due to the applicability of Boolean expressions in breaking modern day encryption, Glyph poses a threat to public key encryption, asymmetric ciphers, and therefore the vast sum of currently implemented cryptosystems. Additionally, due to the prevalence of the Boolean satisfiability problem in various scientific endeavors, Glyph has applicability in Robotics, Artificial Intelligence, DNA research, mathematics, transportation, and similar logistics.

Glyph Form

To avoid having to rely on multiple backtracking operations as a method of minimizing calculation quantity, the Glyph algorithm operates by reducing a Boolean expression to a new format which is referred to as Glyph form. Glyph form relies on acknowledgements that are present in the Boolean expression trees of conventional SAT solvers. Namely, it relies on the associative property of Boolean expressions depicted in the following example.

X0 or X1 or X2 =  (X0 or X1) or X2

The importance of this property statutes that in any given clause of a Boolean Expression in conjunctive normal form (CNF), the previous comparisons within that same clause will always have an impact on the outcome of the current comparison. As such, every time a comparison between two literals is analyzed the previous comparisons must be usably remembered. Glyph form is capable of doing so by converting every single literal of a given Boolean expression in CNF to a series of four nodes. Each node represents a possible state of the literal and the corresponding effect it has on the outcome of the current comparison. Due to the fact that this outcome is consistently kept track of, later comparisons are able to be examined with accurate and encompassing knowledge.

Node structure for A OR –B OR A

Another facet of Glyph form is how it connects these nodes as a method of representing the comparisons provided by operators. Explanatively, every operator in a given Boolean expression in CNF will be converted to a series of connections which are used to connect nodes of adjacent literals to one another. How exactly these connections are applied is determined by the exact orientation of the comparison. In other words, it is determined based on whether the objects being compared are associated with negation operators and whether the comparison is between two literals, two clauses, or a literal and an interval. Nonetheless, there is a limited amount of actual comparison types that exist and as such based on the orientation it is of negligible computation to create these connections. That is to say, in practice there will never be more than eight connections generated for a given comparison.

Node structure for A OR –B OR A with connections

While this method of connecting literals is able to represent solutions for Boolean expressions that do not have repetitive atoms, as soon as such an instance exists its representation becomes flawed. To account for this, every single connection must be recursively associated with atom information. The connections stemming from nodes of the first literal will be associated with atom information provided by those nodes. Later connections that are extensions of those connections will be associated with the atom information of previous connections, as well as additional atom information provided by the current nodes. This will continue throughout the entirety of the expression such that every single connection has appropriate atom information applied to it.

It is important to note that there are minor interruptions in this process to ensure that associations leading to impossible atom information are not exhibited. Explanatively, a connection stemming from one node to another may be associated with an atom that cannot possibly go to the target node, and consequentially this association will merely be dropped from the current connection. Following this procedure enables the issue of variable repetition and collision to be avoided with minimum effort. The completion of this procedure, and the aforementioned procedures, will reduce a given Boolean expression into Glyph form.

Solution Determination

To determine satisfiable solutions to a Boolean expression, Glyph form must be operated on such that connections and associations which do not flow throughout the entirety of the expression are removed. When associations which were considered impossible due to how their connections went to nodes with certain definitions removed, it instituted a potential for the same atom information associated with the previous connection to reach a dead end. Here, a dead end is defined to be a situation where a given atom definition associated with a connection leads to a node that has connections which are not associated with that particular atom definition. The following example illustrates this occurrence.

In this occurrence, three nodes are connected to each other through connections. Every node association in a connection is illustrated as a separate line. The red line in the example represents an atom association that was determined to be impossible, and as such that association was removed from the connection. However, this same atom association still exists in the previous connection, and it now is absent of any continuation. Since it has no options for continuation and is unable to flow through the remainder of the expression, it is considered a dead end.

These dead ends must be removed from Glyph form in order for it to be an accurate representation of satisfiable interpretations to the Boolean expression it has been engineered to represent. To do this, whenever there is a dead end the atom information associated with a connection that is responsible for this dead end will be removed. If this operation begins with the right side of the equation, every time an association leading to a dead end is removed from a connection, it has the potential to create more dead ends. By continually removing any dead ends that exist until the beginning of the problem is reached, Glyph form will be revised to accurately represent satisfiable interpretations to the given Boolean expression.

Interpretation of Data

The data given by these operations will be a series of nodes which stem to nodes of adjacent literals through a series of connections. In order to extract solutions, these connections will be used as “paths.” In that, it is meant that every single possible method of following these paths will be considered a solution to the Boolean expression.  If upon completion of the culling process there do not exist any possible paths, there are zero solutions to the given Boolean expression and it must be considered unsatisfiable.