1,537
views
0
recommends
+1 Recommend
1 collections
    0
    shares

      Celebrating 65 years of The Computer Journal - free-to-read perspectives - bcs.org/tcj65

      scite_
       
      • Record: found
      • Abstract: found
      • Conference Proceedings: found
      Is Open Access

      A Hardware Relaxation Paradigm for Solving NP-Hard Problems

      proceedings-article
      , , , ,
      Visions of Computer Science - BCS International Academic Conference (VOCS)
      BCS International Academic Conference
      22 - 24 September 2008
      NP-hard problem, Boolean satisfiability, Digital circuit with feedback, Relaxation, Simulated annealing
      Bookmark

            Abstract

            Digital circuits with feedback loops can solve some instances of NP-hard problems by relaxation: the circuit will either oscillate or settle down to a stable state that represents a solution to the problem instance. This approach differs from using hardware accelerators to speed up the execution of deterministic algorithms, as it exploits stabilisation properties of circuits with feedback, and it allows a variety of hardware techniques that do not have counterparts in software. A feedback circuit that solves many instances of Boolean satisfiability problems is described, with experimental results from a preliminary simulation using a hardware accelerator.

            Content

            Author and article information

            Conference
            September 2008
            September 2008
            : 75-86
            Affiliations
            [0001]Department of Computing Science, University of Glasgow
            Article
            10.14236/ewic/VOCS2008.8
            6c69de93-8697-4443-888f-4eba0840e20f
            © Paul Cockshott et al. Published by BCS Learning and Development Ltd. Visions of Computer Science - BCS International Academic Conference

            This work is licensed under a Creative Commons Attribution 4.0 Unported License. To view a copy of this license, visit http://creativecommons.org/licenses/by/4.0/

            Visions of Computer Science - BCS International Academic Conference
            VOCS
            Imperial College, London, UK
            22 - 24 September 2008
            Electronic Workshops in Computing (eWiC)
            BCS International Academic Conference
            History
            Product

            1477-9358 BCS Learning & Development

            Self URI (article page): https://www.scienceopen.com/hosted-document?doi=10.14236/ewic/VOCS2008.8
            Self URI (journal page): https://ewic.bcs.org/
            Categories
            Electronic Workshops in Computing

            Applied computer science,Computer science,Security & Cryptology,Graphics & Multimedia design,General computer science,Human-computer-interaction
            NP-hard problem,Relaxation,Boolean satisfiability,Simulated annealing,Digital circuit with feedback

            Comments

            Comment on this article