پیش‌نویس:مسئله یک‌ریختی گروه

از ویکی‌پدیا، دانشنامهٔ آزاد

در جبر مجرد، مسئله یک‌ریخیتی گروه یک مسئله تصمیم است که به بررسی وجود دو نمایش متناهی از گروه برای اشاره به یک گروه یک‌ریخت می‌پردازد.

مسئله یک‌ریختی توسط ماکس دن صورت‌بندی شده است و همراه با مسئله واژه‌ برای گروه و مسئله مزدوج برای گروه، یکی از سه مسئله بنبادی تصمیم در نظریه گروه‌ها است که در سال ۱۹۱۱ طرح شده است. هر سه مسئله تصمیم‌ناپدیرند و فارغ از زمان اجرا، هیچ الگوریتم رایانش‌پذیری که برای هر نمونه مسئله یک‌ریختی پاسخی صحیح داشته باشد، وجود ندارد. در حقیقت، مسئله تصمیم این موضوع که آیا یک گروه بدیهی است، تصمیم‌ناپذیر است که این موضوع خود از نتایج قضیه آدیان - رابین، اثر سرگئی آدیان و مایکل رابین است.

مسئله یک‌ریختی گروه که در آن گروه‌ها با جداول گوناگونی نمایش داده می‌شوند، کاهش‌پذیر به مسئله یک‌ریختی گراف است، اما عکس این موضوع صادق نیست. هر دو مسئله دارای الگوریتم‌های شبه‌ چند جمله‌ای هستند که این الگوریتم‌ها ابتدا توسط رابرت تارجان (۱۹۷۸) و سپس لاسلو بابایی (۲۰۱۵) ارائه شده است.