Sublinear P system solutions to NP-complete problems Article Swipe
Related Concepts
Michael J. Dinneen
,
Alec Henderson
,
Radu Nicolescu
·
YOU?
·
· 2023
· Open Access
·
· DOI: https://doi.org/10.1016/j.tcs.2023.113848
· OA: W4362634829
YOU?
·
· 2023
· Open Access
·
· DOI: https://doi.org/10.1016/j.tcs.2023.113848
· OA: W4362634829
cP systems have been shown to very e ciently solve many NP-complete problems, \ni.e. in linear time. However, these solutions have been independent of each other and \nhave not utilised the theory of reductions. This work presents a sublinear solution to \nk-SAT and demonstrates that k-colouring can be reduced to k-SAT in constant time. \nThis work demonstrates that traditional reductions are e cient in cP systems and that \nthey can sometimes produce more e cient solutions than the previous problem-speci c \nsolutions.
Related Topics
Finding more related topics…