Solving a new NP-Complete problem that resembles image pattern recognition using deep learning
(1) Saint Mary's Catholic Academy
https://doi.org/10.59720/21-014
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: