University of Hertfordshire Research Archive

        JavaScript is disabled for your browser. Some features of this site may not work without it.

        Browse

        All of UHRABy Issue DateAuthorsTitlesThis CollectionBy Issue DateAuthorsTitles

        Arkivum Files

        My Downloads
        View Item 
        • UHRA Home
        • University of Hertfordshire
        • Research publications
        • View Item
        • UHRA Home
        • University of Hertfordshire
        • Research publications
        • View Item

        An assertion concerning functionally complete algebras and NP-completeness

        Author
        Horvath, G.
        Nehaniv, C.L.
        Czabo, C.
        Attention
        2299/6032
        Abstract
        In a paper published in J. ACM in 1990, Tobias Nipkow asserted that the problem of deciding whether or not an equation over a nontrivial functionally complete algebra has a solution is NP-complete. However, close examination of the reduction used shows that only a weaker theorem follows from his proof, namely that deciding whether or not a system of equations has a solution is NP-complete over such an algebra. Nevertheless, the statement of Nipkow is true as shown here. As a corollary of the proof we obtain that it is coNP-complete to decide whether or not an equation is an identity over a nontrivial functionally complete algebra.
        Publication date
        2008
        Published in
        Theoretical Computer Science
        Published version
        https://doi.org/10.1016/j.tcs.2008.08.028
        Other links
        http://hdl.handle.net/2299/6032
        Metadata
        Show full item record

        Related items

        Showing items related by title, author, creator and subject.

        • A Complete Study of Radio Galaxies at z ~ 0.5 

          Herbert, Peter David (2013-04-10)
          In this thesis I investigate the hosts and cluster environments of a sample of 41 radio galaxies between z = 0.4 and z = 0.6. I use spectroscopic data for a 24 object subsample to investigate their star formation histories ...
        • Complete Communities or Dormitory Towns? Case Studies in Interwar Housing at Welwyn Garden City, Becontree and St Helier 

          Benjamin, Matthew (2016-11-23)
          Housing has always been a paramount issue; in the late nineteenth and early twentieth century attempts were made to revolutionise the problem of poor quality houses and the accompanying poor quality of life. This was set ...
        • Erratum to: The complete nucleotide sequence of a totivirus from Aspergillus foetidus (Arch Virol, 10.1007/s00705-012-1368-x) 

          Kozlakidis, Z.; Herrero, N.; Coutts, Robert H.A. (2013-02)
        Keep in touch

        © 2019 University of Hertfordshire

        I want to...

        • Apply for a course
        • Download a Prospectus
        • Find a job at the University
        • Make a complaint
        • Contact the Press Office

        Go to...

        • Accommodation booking
        • Your student record
        • Bayfordbury
        • KASPAR
        • UH Arts

        The small print

        • Terms of use
        • Privacy and cookies
        • Criminal Finances Act 2017
        • Modern Slavery Act 2015
        • Sitemap

        Find/Contact us

        • T: +44 (0)1707 284000
        • E: ask@herts.ac.uk
        • Where to find us
        • Parking
        • hr
        • qaa
        • stonewall
        • AMBA
        • ECU Race Charter
        • disability confident
        • AthenaSwan