Henderson, ANicolescu, RDinneen, MJ2023-01-242023-01-242022CDMTCS Research Reports CDMTCS-559 (2022)1178-3540https://hdl.handle.net/2292/62554cP 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.Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated. Previously published items are made available in accordance with the copyright policy of the publisher.https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmTechnical ReportFields of ResearchCopyright: The author(s)http://purl.org/eprint/accessRights/OpenAccess