Brunker, Jess_MCS_2022

Title Brunker, Jess_MCS_2022
Alternative Title Evaluating P VS NP Using Graph Neural Networks
Creator Brunker, Jess
Collection Name Master of Computer Science
Description The following Master of Computer Science thesis explores P VS NP using graph neural networks as an evaluation tool.
Abstract The question of P versus NP asks if all problems that have polynomial-time algorithms for verifying that a solution is correct also have polynomial-time algorithms for finding a solution. Many NP problems are graph-related and have variants in P. Graph neural networks (GNNs) are used for representation learning on graph-structured data by aggregating information from local structures in the graph at a node level, then pooling that information together to learn information about the graph itself. Using GNN models, we seek to determine how the differences in problem complexity (P versus NP) translate to machine learning model performance and complexity, using the graph coloring and Boolean satisfiability (SAT) problems for the datasets. Multiple datasets are generated for each problem, varying in both problem size and size of the training set. As expected, models trained on the P datasets had significantly higher performance when compared to models trained on similar NP datasets, and were less dependent on the size of the training set. Both graph representations of the SAT problem failed to achieve decent performance on the NP variants, so an analysis of how the difficulty increases with problem size is limited. However, the results on the graph coloring problem show that the performance decreased at a similar rate as the problem grows in size for both the P and NP variants. We also showed that increasing the power of the GNN model increased its performance on the NP datasets, but it was not enough to overcome the lack of training data.
Subject Computer science; Neural networks (Computer science); Computational complexity
Keywords P vs NP; datasets; graph neural networks; computer science; Boolean satisfiability
Digital Publisher Stewart Library, Weber State University, Ogden, Utah, United States of America
Date 2022
Medium Thesis
Type Text
Access Extent 35 page PDF; 1.36 MB
Language eng
Rights The author has granted Weber State University Archives a limited, non-exclusive, royalty-free license to reproduce their theses, in whole or in part, in electronic or paper form and to make it available to the general public at no charge. The author retains all other rights.
Source University Archives Electronic Records; Master of Computer Science. Stewart Library, Weber State University
OCR Text Show
Format application/pdf
ARK ark:/87278/s6knfxg6
Setname wsu_smt
ID 96875
Reference URL https://digital.weber.edu/ark:/87278/s6knfxg6