Linear Algorithm for Regular Expressions within P vs. NP Question

Read the full article See related articles

Discuss this preprint

Start a discussion What are Sciety discussions?

Listed in

This article is not in any list yet, why not save it to one of your lists.
Log in to save this article

Abstract

We present an almost polynomial matching algorithm for regular expressions with extensions like intersection, complement and subtraction which runs in practically applicable time and space, which outperforms any existing methods to the present time and converges to the theoretically known minimal lower bound, thus, making the extended regular expression matching almost practical in the main-stream domain as regular expressions are widely used to the present time and can be used, for instance, in parsing techniques or other well-known problems like matching of high-size input strings in any practical domains to the present time as originally regular expressions were developed to make it possible, it still needs a better approach for extended sub-problem like match with extended operators as intersection, complement and subtraction. Since our exhibition of the equivalence of complexity classes, we have met that they are still not giving correct and coherent solution for problems known as unsolvable or NP-complete by Cook-Levin theorem “P versus NP”, in contrary, in this work we present the proof of nonequivalent relation between polynomial and non-polynomial classes and show that NP-complete problem cannot be approximated or solved on a hypothetical computational device within the proof by contradiction

Article activity feed