Solving a new NP-Complete problem that resembles image pattern recognition using deep learning

(1) Saint Mary's Catholic Academy

In computer science, non-deterministic polynomialtime

(NP) denotes the set of problems for which a

solution might or might not be found quickly but can

be checked quickly. We also call the set of problems

in NP that are at least as hard as any other NP problem

non-deterministic polynomial-time complete (NPcomplete).

Although not known if they can be solved

quickly, NP-complete problems can be converted

into one another quickly. A prominent and practical

example is the protein folding problem, which is a

problem of determining the shape and function of

proteins. In this paper, we discovered and provided

a mathematical proof of a new NP-complete problem,

that we named 3-Grid Pattern Decision Problem (3-

GPDP). 3-GPDP is a decision problem that asks if a

specific kind of pattern exists or not on a grid/matrix

of numbers consisting of zeros and ones, much like

image recognition. We hypothesized that a neural net

would be able to solve 3-GPDP problems with high

accuracy and low loss when trained. In support of

our hypothesis, our experiment resulted in a neural

net that performed with 84% accuracy and 0.14 loss

without underfitting or overfitting. Moreover, there

was also an increase in accuracy and decrease in

loss with more training data. As a result, since neural

networks are effective at solving 3-GPDP problems,

which are NP-complete, then we can convert important

NP-complete problems into 3-GPDP problems, solve

the 3-GPDP problems using neural networks, and

convert the solution back to the solution of the initial

problem, quickly.

This article has been tagged with: