Berman–Hartmanis conjecture
ساختی پیچیدگی کے نظریہ میں، برمن-ہارٹ مینس قیاس ایک غیر حل شدہ قیاس ہے جس کا نام لیونارڈ سی برمن اور جورس ہارٹ مینس کے نام پر رکھا گیا ہے جس میں کہا گیا ہے کہ تمام این پی مکمل زبانیں ایک جیسی نظر آتی ہیں، اس معنی میں کہ وہ کثیر الجہتی وقت آئسومورفزم کے ذریعہ ایک دوسرے سے متعلق ہوسکتی ہیں۔ رسمی زبانوں L1 اور L2 کے درمیان ایک آئسومورفزم L1 کے حروف تہجی میں تاروں سے لے کر L2 کے حروف تہجی میں تاروں تک کا ایک دو طرفہ نقشہ ہے، اس خاصیت کے ساتھ کہ ایک تار x کا تعلق L1 سے ہے اگر اور صرف اس صورت میں جب f (x) کا تعلق L2 سے ہو۔ یہ ایک کثیر الجہتی وقت آئسومورفزم (یا مختصر طور پر پی-آئسومورفزم) ہے اگر f اور اس کے الٹا فعل دونوں کو ان کے دلائل کی لمبائی میں وقت کی کثیر الجہتی مقدار میں شمار کیا جا سکتا ہے۔ مشاہدہ کیا گیا کہ اس وقت این پی مکمل ہونے کے لیے جانی جانے والی تمام زبانیں پی-آئسومورفک تھیں۔ مزید مضبوطی سے، انہوں نے مشاہدہ کیا کہ اس وقت کی تمام معروف این پی مکمل زبانیں پیڈ ایبل تھیں، اور انہوں نے ثابت کیا (مائی ہل آئسومورفزم تھیوریم کے مطابق) کہ پیڈ ایبل این پی مکمل زبانوں کے تمام جوڑے پی-آئسومورفک ہیں۔ اگر کثیر الجہتی ٹائم فنکشن f (x, y) کثیر الجہتی ٹائم انورس کے ساتھ ہو اور اس خاصیت کے ساتھ کہ، تمام x اور y کے لیے، x کا تعلق L سے ہو اگر اور صرف اس صورت میں جب f (x, y) L سے تعلق رکھتا ہو: یعنی، ان پٹ x کو غیر متعلقہ معلومات y کے ساتھ، غیر متغیر طریقے سے، زبان میں اس کی رکنیت کو تبدیل کیے بغیر پیڈ کرنا ممکن ہے۔ ان نتائج کی بنیاد پر، برمن اور ہارٹ مینس نے قیاس کیا کہ تمام این پی مکمل زبانیں پی-آئسومورفک ہیں۔ چونکہ پی-آئسومورفزم پیڈ ایبلٹی کو محفوظ رکھتا ہے، اور پیڈ ایبل این پی-مکمل زبانیں موجود ہیں، اس لیے برمن-ہارٹ مینس قیاس کو بیان کرنے کا ایک مساوی طریقہ یہ ہے کہ تمام این پی-مکمل زبانیں پیڈ ایبل ہیں۔ پولینومیل ٹائم آئسومورفزم ایک مساوات کا رشتہ ہے، اور اسے رسمی زبانوں کو مساوات کی کلاسوں میں تقسیم کرنے کے لیے استعمال کیا جا سکتا ہے، اس لیے برمن-ہارٹمینس قیاس کو بیان کرنے کا ایک اور طریقہ یہ ہے کہ این پی مکمل زبانیں اس تعلق کے لیے ایک واحد مساوات کی کلاس بناتی ہیں۔ مضمرات اگر برمن-ہارٹ مینس کا قیاس درست ہے تو اس کا فوری نتیجہ شاذ و نادر این پی-مکمل زبانوں کا عدم وجود ہوگا، یعنی وہ زبانیں جن میں لمبائی n کے ہاں-مثالوں کی تعداد صرف n کے فعل کے طور پر کثیر الجہتی طور پر بڑھتی ہے۔ معروف این پی-مکمل زبانوں میں ہاں-مثالوں کی ایک بڑی تعداد ہوتی ہے جو تیزی سے بڑھتی ہے، اور اگر ایل ایک ایسی زبان ہے جس میں تیزی سے بہت سی ہاں-مثالوں کے ساتھ ہے تو یہ ایک شاذ و نادر زبان کے لیے پی-آئسومورفک نہیں ہو سکتی، کیونکہ نقشہ سازی کو ایک سے ایک ہونے کے لیے اس کے ہاں-مثالوں کو ان تاروں سے نقشہ بنانا ہوگا جو کثیر الجہتی طور پر طویل سے زیادہ ہیں۔ اس کے نتیجے میں غیر معمولی این پی-مکمل زبانوں کی عدم موجودگی کا مطلب یہ ہے کہ پی ष्णپ، کیونکہ اگر پی = این پی ہے تو پی میں ہر غیر معمولی زبان (بشمول کچھ غیر معمولی زبانیں، جیسے کہ بائنری سٹرنگ کی زبان جن کے تمام بٹس صفر ہیں) این پی-مکمل ہوں گی۔ 1982 میں، اسٹیو مہانے نے اپنا ثبوت شائع کیا کہ غیر معمولی این پی-مکمل زبانوں کا عدم وجود (این پی-تکمیل کے ساتھ معیاری طریقے سے کئی ایک تخفیف کا استعمال کرتے ہوئے بیان کیا گیا ہے) حقیقت میں اس بیان کے مساوی ہے کہ پی  ऒत्त این پی ؛ یہ مہانے کا نظریہ ہے۔ یہاں تک کہ ٹورنگ کٹوتیوں کا استعمال کرتے ہوئے این پی-تکمیل کی ایک آرام دہ تعریف کے لیے، ایک غیر معمولی این پی-مکمل زبان کا وجود کثیر الجہتی درجہ بندی کے غیر متوقع خاتمے کا اشارہ کرے گا۔ قیاس آرائی کی طرف ثبوت کے طور پر، یہ ظاہر ہوتا ہے کہ ایک محدود قسم کی کمی کے ساتھ ایک مماثل قیاس درست ہے: ہر دو زبانیں جو AC0 کئی-ایک کمی کے تحت NP کے لیے مکمل ہیں، AC0 آئسومورفزم رکھتی ہیں۔ اس سے پتہ چلتا ہے کہ، اگر یک طرفہ افعال موجود ہیں جنہیں تمام ان پٹ پر کثیر الجہتی وقت میں الٹا نہیں کیا جا سکتا، لیکن اگر اس طرح کے ہر فنکشن میں ان پٹ کا ایک چھوٹا لیکن گھنے ذیلی سیٹ ہے جس پر اسے P/پولی میں الٹا کیا جا سکتا ہے (جیسا کہ اس قسم کے معروف افعال کے لیے درست ہے) تو ہر دو NP-مکمل زبانوں میں P/پولی آئسومورفزم ہوتا ہے۔ اور ایک اوریکل مشین ماڈل پایا جس میں آئسومورفزم قیاس آرائی کا ینالاگ درست ہے۔ قیاس آرائی کے خلاف ثبوت اور کے ذریعہ فراہم کیا گیا تھا۔ جوزف اور ینگ نے این پی مکمل مسائل کی ایک کلاس متعارف کرائی، کے-تخلیقی سیٹ، جس کے لیے معیاری این پی مکمل مسائل کے لیے کوئی پی-آئسومورفزم معلوم نہیں ہے۔ کرٹز اور دیگر۔ اس سے پتہ چلتا ہے کہ اوریکل مشین ماڈلز میں بے ترتیب اوریکل تک رسائی دی جاتی ہے، قیاس کا ینالاگ درست نہیں ہے: اگر A ایک بے ترتیب اوریکل ہے، تو NPA کے لیے مکمل ہونے والے تمام سیٹوں میں PA میں آئسومورفزم نہیں ہوتے ہیں۔ بے ترتیب اوریکلز عام طور پر کرپٹوگرافی کے نظریہ میں کرپٹوگرافک ہیش افعال کو ماڈل بنانے کے لیے استعمال ہوتے ہیں جو بے ترتیب سے کمپیوٹیشنل طور پر ناقابل شناخت ہوتے ہیں، اور کرٹز اور دیگر کی تعمیر۔ اوریکل کی جگہ اس طرح کے فنکشن کے ساتھ انجام دیا جا سکتا ہے۔ اس وجہ سے، دوسروں کے درمیان، برمن-ہارٹمینس آئسومورفزم قیاس آرائی کو بہت سے پیچیدگی تھیوریسٹوں کے ذریعہ غلط سمجھا جاتا ہے۔ ساختی پیچیدگی کا نظریہ قیاس کرتا ہے کہ کمپیوٹر سائنس میں حل نہ ہونے والے مسائل ریاضی میں حل نہ ہونے والے مسائل