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
        • PhD Theses Collection
        • View Item
        • UHRA Home
        • University of Hertfordshire
        • PhD Theses Collection
        • View Item

        Functions and Polynomials over Finite Groups from the Computational Perspective

        View/Open
        Download fulltext (PDF, 1020Kb)
        Author
        Horvath, G.
        Attention
        2299/2000
        Abstract
        In the thesis we investigate the connections between arbitrary functions and their realizing polynomials over finite algebras. We study functionally complete algebras, i.e. algebras over which every function can be realized by a polynomial expression. We characterize functional completeness by the so called Stone-Weierstrass property, and we determine the functionally complete semigroups and semirings. Then we investigate the computational perspective of the function-polynomial relationships over finite groups. We consider the efficient representability, the equivalence, and the equation solvability problems. We approach the efficient representability problem from three directions. We consider the length of functions, we investigate the circuit complexity of functions, and we analyse the finite-state sequential machine representation of Boolean functions. From each of these viewpoints we give bounds on the potential efficiency of computations based on functionally complete groups compared to computations based on the two-element Boolean algebra. Neither the equivalence problem nor the equation solvability problem has been completely characterized for finite groups. The complexity of the equivalence problem was only known for nilpotent groups. In the thesis we determine the complexity of the equivalence problem for certain meta-Abelian groups and for all non-solvable groups. The complexity of the equation solvability problem is known for nilpotent groups and for non-solvable groups. There are no results about the complexity of the equation solvability problem for solvable non-nilpotent groups apart from the case of certain meta-cyclic groups that we present in the thesis. Moreover, we determine the complexity of the equation solvability problem for all functionally complete algebra. The idea of the extended equivalence problem emerges from the observation that the commutator might significantly change the length of group-polynomials. We characterize the complexity of the extended equivalence problem for finite groups. For many finite groups we determine the complexity of the equivalence problem if the commutator is considered as the basic operation of the group.
        Publication date
        2008-05-07
        Other links
        http://hdl.handle.net/2299/2000
        Metadata
        Show full item record
        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