Original title: Testování identit
Translated title: Identity checking
Authors: Polach, František ; Žemlička, Jan (referee) ; Stanovský, David (advisor)
Document type: Bachelor's theses
Year: 2006
Language: cze
Abstract: Nazev prace: Testovdni identit Autor: FrantiSek Polnch Katedra (ustav): Katedra algebry Vedouci bakalafske prace: RNDr. David Stanovsky, Ph.D. e-mail vedouciho: stanovsk@karlin.mff.citni.cz Abstrakt: Na overeni, zda dana identita (napf. komlttativita, asociativita, apod.) plati v dane algebre (grupe, okrului,...), existuje ocividny algoritmtts, ktery ma exponencidlni slozitost vzh- ledem kdelce zadane identity (profixm'algebru)- Neni tezke nahlednout, ze tento problemje pro libovolnou algebra v I ride co-NP a ze existuji algebry, pro ktere je co-NP-uplny. Na druhou stranu, pro mnoho algeber (napr. pro abelovske grupy) existitje algoritmus polynomidlni. Ex- istuje mezindrodni projekt, jehoz cilein je charakterizovat ty algebry, pro ktere je tento prob- lem pollfnomidlni, rcsp. co-NP-iiplny. Cflem tcto prdceje shrnout nektere zndme vysledky o grupdch a okruzich. Konkretne ukdzeme polynomidlni algoritmy pro testovdni identit v nilpo- tentnich i dihedrdlnfch grupdch a nilpotentnich okruzich, a dokdzeme co-NP-iiplnost testovdni identit v nenilpotcntnfch okruzich. Klicova slova: testovdni identit, slozitost, grupy, okruhy Title: Identity checking Author: Franlisek Polach Department: Department of Algebra Supervisor: RNDr. David Stanovsky, Ph.D. Supervisor's e-mail address: stanovsk@karlin.inff.cuni.cz Abstract:...

Institution: Charles University Faculties (theses) (web)
Document availability information: Available in the Charles University Digital Repository.
Original record: http://hdl.handle.net/20.500.11956/5810

Permalink: http://www.nusl.cz/ntk/nusl-272006


The record appears in these collections:
Universities and colleges > Public universities > Charles University > Charles University Faculties (theses)
Academic theses (ETDs) > Bachelor's theses