Simplicial complex recognition problem
سادہ پیچیدہ شناخت کا مسئلہ الجبرائی ٹوپولوجی میں ایک کمپیوٹیشنل مسئلہ ہے۔ ایک سادہ کمپلیکس کو دیکھتے ہوئے، مسئلہ یہ طے کرنا ہے کہ آیا یہ کسی دوسرے فکسڈ سادہ کمپلیکس کے لیے ہومومورفک ہے یا نہیں۔ طول و عرض 5 یا اس سے زیادہ کے کمپلیکس کے لیے مسئلہ ناقابل فیصلہ ہے۔ پس منظر ایک تجریدی سادہ کمپلیکس (اے ایس سی) سیٹوں کا خاندان ہے جو ذیلی سیٹوں کے تحت بند ہوتا ہے (خاندان میں کسی سیٹ کا ذیلی سیٹ بھی خاندان میں ایک سیٹ ہوتا ہے)۔ ہر تجریدی سادہ کمپلیکس میں جیومیٹرک آسان کمپلیکس (جی ایس سی) کے طور پر یوکلڈین اسپیس میں ایک منفرد جیومیٹرک احساس ہوتا ہے، جہاں اے ایس سی میں کے عناصر کے ساتھ ہر سیٹ کو جی ایس سی میں (کے-1) جہتی سمپلیکس میں نقشہ بنایا جاتا ہے۔ اس طرح، اے ایس سی کسی ہندسی شے کی محدود نمائندگی فراہم کرتا ہے۔ اے ایس سی کو دیکھتے ہوئے، کوئی بھی جی ایس سی کی ٹوپولوجی کے بارے میں کئی سوالات پوچھ سکتا ہے جس کی وہ نمائندگی کرتا ہے۔ ہومیومورفزم کا مسئلہ ہومیومورفزم کا مسئلہ یہ ہے کہ: ہموار کئی گنا کی نمائندگی کرنے والے دو محدود سادہ کمپلیکس کو دیکھتے ہوئے، فیصلہ کریں کہ آیا وہ ہومیومورفک ہیں۔ اگر کمپلیکس زیادہ سے زیادہ 3 طول و عرض کے ہوں، تو مسئلہ فیصلہ کن ہے۔ یہ جیومیٹریزیشن قیاس کے ثبوت سے ملتا ہے۔ ہر d ≤ 4 کے لیے، d-جہتی سادہ کمپلیکس کے لیے ہومومورفزم کا مسئلہ ناقابل فیصلہ ہے۔ یہی بات سچ ہے اگر "ہومیومورفک" کو "پیس وائز-لکیری ہومیومورفک" سے تبدیل کیا جائے۔ شناخت کا مسئلہ شناخت کا مسئلہ ہومومورفزم کے مسئلے کا ایک ذیلی مسئلہ ہے، جس میں ایک سادہ کمپلیکس کو فکسڈ پیرامیٹر کے طور پر دیا جاتا ہے۔ ان پٹ کے طور پر ایک اور آسان کمپلیکس کو دیکھتے ہوئے، مسئلہ یہ فیصلہ کرنا ہے کہ آیا یہ دی گئی فکسڈ کمپلیکس کے لیے ہومومورفک ہے یا نہیں۔ شناخت کا مسئلہ 3 جہتی دائرے کے لیے فیصلہ کن ہے۔ یعنی، ایک الگورتھم ہے جو یہ فیصلہ کر سکتا ہے کہ آیا کوئی دیا ہوا سادہ کمپلیکس 4 جہتی گیند کی حد کے لیے ہومومورفک ہے یا نہیں۔ شناخت کا مسئلہ کسی بھی d ≤ 5 کے لیے d-جہتی دائرے کے لیے ناقابل فیصلہ ہے۔ اس کا ثبوت گروپوں کے لیے لفظ مسئلہ کو کم کرنا ہے۔ اس سے یہ ثابت کیا جا سکتا ہے کہ شناخت کا مسئلہ کسی بھی فکسڈ کمپیکٹ ڈی-ڈائیمینشنل کئی گنا کے لیے ناقابل فیصلہ ہے۔ 2014 تک، یہ کھلا ہے کہ آیا شناخت کا مسئلہ 4 جہتی دائرے کے لیے فیصلہ کن ہے یا نہیں۔ کئی گنا مسئلہ یہ ہے کہ: ایک محدود سادہ کمپلیکس کو دیکھتے ہوئے، کیا یہ کئی گنا ہومومورفک ہے؟ مسئلہ ناقابل فیصلہ ہے ؛ اس کا ثبوت گروپوں کے لیے لفظ مسئلہ کو کم کرنا ہے۔ حوالہ جات ناقابل فیصلہ مسائل سادہ سیٹ