I will survey results about computational complexity of the word
problem in groups and its relation with isoperimetric function and other
asymptotic
geometry invariants of groups. A typical result (joint with Birget,
Olshanskii, Rips):
the word problem of a finitely generated group is in NP if and only if the
group
embeds into a finitely presented group with polynomial isoperimetric
function.
Mark Sapir studoval ve Sverdlovsku (nyní Jekaterinburg) a v Moskvě. Ihned po
doktorátu pracoval jako docent na universitě ve Sverdlovsku a od roku 1991 v
USA. V
současnosti je Centennial professor na Vanderbiltově universitě v Nashvillu.
Mark
Sapir byl hostem předních mezinárodních ústavů, mezi nimiž zmiňme opakované
pobyty na IHES Bur-Sur-Yvette, na Max Planckově institutu v Bonnu, Hebrejské
universitě v Jeruzalémě a zmiňme rovněž Simmonsovu profesuru na MSRI v Ber-
keley. Mark Sapir je členem redakčních rad 5 mezinárodních časopisů. V roce
2006
přednesl zvanou přednášku na Mezinárodním kongresu matematiků v Madridu.
Přes jeho mnohostrannou činnost lze říci, že hlavním oborem Marka Sapira
je
teorie grup, zvláště pak geometrická a asymptotická teorie grup včetně
souvisejících
algoritmických problémů. Z této oblasti je jeho pražské kolokvium.
Zmiňme však také, že Mark Sapir je i známým autorem pedagogicky
zaměřených
textů a software. Je též velmi aktivní při výchově mladých nadaných
informatiků a
matematiků, jak na úrovni gymnázií tak universitní. Jeho učebnice
informatiky pro
střední školy z roku 1990 vyšla v mnoha vydáních a celkový náklad překročil
2 mil.
výtisků. To je u matematického a informatického textu nevídané!