Abstract:
cP systems have been shown to very e ciently solve many NP-complete problems,
i.e. in linear time. However, these solutions have been independent of each other and
have not utilised the theory of reductions. This work presents a sublinear solution to
k-SAT and demonstrates that k-colouring can be reduced to k-SAT in constant time.
This work demonstrates that traditional reductions are e cient in cP systems and that
they can sometimes produce more e cient solutions than the previous problem-speci c
solutions.