Sublinear P system solutions to NP-complete problems

Show simple item record Henderson, A en Nicolescu, R en Dinneen, MJ en 2023-01-24T23:04:43Z 2023-01-24T23:04:43Z 2022 en
dc.identifier.citation CDMTCS Research Reports CDMTCS-559 (2022) en
dc.identifier.issn 1178-3540 en
dc.description.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.
dc.publisher Department of Computer Science, The University of Auckland, New Zealand en
dc.relation.ispartofseries CDMTCS Research Report Series en
dc.rights 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. en
dc.rights.uri en
dc.source.uri en
dc.title Sublinear P system solutions to NP-complete problems en
dc.type Technical Report en
dc.subject.marsden Fields of Research en
dc.rights.holder Copyright: The author(s) en
dc.rights.accessrights en

Files in this item

Find Full text

This item appears in the following Collection(s)

Show simple item record


Search ResearchSpace