Sublinear P system solutions to NP-complete problems

Show simple item record

dc.contributor.author Henderson, A en
dc.contributor.author Nicolescu, R en
dc.contributor.author Dinneen, MJ en
dc.date.accessioned 2023-01-24T23:04:43Z
dc.date.available 2023-01-24T23:04:43Z
dc.date.issued 2022 en
dc.identifier.citation CDMTCS Research Reports CDMTCS-559 (2022) en
dc.identifier.issn 1178-3540 en
dc.identifier.uri https://hdl.handle.net/2292/62554
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 https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm en
dc.source.uri https://www.cs.auckland.ac.nz/research/groups/CDMTCS/researchreports/index.php 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 http://purl.org/eprint/accessRights/OpenAccess en


Files in this item

Find Full text

This item appears in the following Collection(s)

Show simple item record

Share

Search ResearchSpace


Browse

Statistics