Berman–Hartmanis conjecture
কাঠামোগত জটিলতা তত্ত্বে, বার্মান-হার্টমানিস অনুমান হল লিওনার্ড সি বার্মান এবং জুরিস হার্টমানিসের নামে নামকরণ করা একটি অমীমাংসিত অনুমান যা বলে যে সমস্ত এনপি-সম্পূর্ণ ভাষাগুলি দেখতে একই রকম, এই অর্থে যে তারা বহুপদী সময় সমরূপতা দ্বারা একে অপরের সাথে সম্পর্কিত হতে পারে। বিবৃতি আনুষ্ঠানিক ভাষা এল1 এবং এল2-এর মধ্যে একটি সমরূপতা হল এল1 বর্ণমালার স্ট্রিং থেকে এল2 বর্ণমালার স্ট্রিং পর্যন্ত একটি বাইজেক্টিভ মানচিত্র, যার বৈশিষ্ট্য হল যে একটি স্ট্রিং এক্স এল1-এর অন্তর্গত যদি এবং শুধুমাত্র যদি এফ (এক্স) এল2-এর অন্তর্গত হয়। এটি একটি পলিনোমিয়াল টাইম আইসোমরফিজম (বা সংক্ষেপে পি-আইসোমরফিজম) যদি f এবং এর বিপরীত ফাংশন উভয়ই তাদের আর্গুমেন্টের দৈর্ঘ্যের সময় পলিনোমিয়ালে গণনা করা যায়। পর্যবেক্ষণ করা হয়েছে যে সেই সময়ে এনপি-সম্পূর্ণ হিসাবে পরিচিত সমস্ত ভাষা পি-আইসোমরফিক ছিল। আরও দৃঢ়ভাবে, তারা পর্যবেক্ষণ করেছেন যে তৎকালীন সমস্ত পরিচিত এনপি-সম্পূর্ণ ভাষাগুলি প্যাডেবল ছিল এবং তারা প্রমাণ করেছে (মাইল আইসোমরফিজম উপপাদ্যের অনুরূপ) যে প্যাডেবল এনপি-সম্পূর্ণ ভাষাগুলির সমস্ত জোড়া পি-আইসোমরফিক। একটি ভাষা L প্যাডেবল হয় যদি একটি বহুপদী সময় ফাংশন f (x, y) থাকে যার একটি বহুপদী সময় বিপরীত হয় এবং এই বৈশিষ্ট্য সহ যে, সমস্ত x এবং y-এর জন্য, x L-এর অন্তর্গত হয় যদি এবং শুধুমাত্র যদি f (x, y) L-এর অন্তর্গত হয়ঃ অর্থাৎ, অপ্রাসঙ্গিক তথ্য y দিয়ে ইনপুট x-কে প্যাড করা সম্ভব, একটি বিপরীত পদ্ধতিতে, ভাষায় তার সদস্যপদ পরিবর্তন না করে। এই ফলাফলের উপর ভিত্তি করে, বারম্যান এবং হার্টম্যানিস অনুমান করেছিলেন যে সমস্ত এনপি-সম্পূর্ণ ভাষাগুলি পি-আইসোমরফিক। যেহেতু পি-আইসোমরফিজম প্যাডেবিলিটি সংরক্ষণ করে এবং প্যাডেবল এনপি-সম্পূর্ণ ভাষাগুলি বিদ্যমান, তাই বারম্যান-হার্টমানিস অনুমানের একটি সমতুল্য উপায় হল যে সমস্ত এনপি-সম্পূর্ণ ভাষাগুলি প্যাডেবল। বহুপদী সময় সমরূপতা একটি সমতুল্য সম্পর্ক, এবং এটি আনুষ্ঠানিক ভাষাগুলিকে সমতুল্য শ্রেণীতে বিভক্ত করতে ব্যবহার করা যেতে পারে, তাই বারম্যান-হার্টমানিস অনুমানটি বলার আরেকটি উপায় হল যে এনপি-সম্পূর্ণ ভাষাগুলি এই সম্পর্কের জন্য একটি একক সমতুল্য শ্রেণী গঠন করে। প্রভাবগুলি যদি বার্মান-হার্টমানিসের অনুমানটি সত্য হয়, তবে একটি তাৎক্ষণিক পরিণতি হবে বিরল এন. পি-সম্পূর্ণ ভাষাগুলির অস্তিত্ব না থাকা, যথা এমন ভাষাগুলি যেখানে দৈর্ঘ্য এন-এর হ্যাঁ-দৃষ্টান্তের সংখ্যা কেবল এন-এর ফাংশন হিসাবে বহুপদীভাবে বৃদ্ধি পায়। পরিচিত এন. পি-সম্পূর্ণ ভাষাগুলিতে বেশ কয়েকটি হ্যাঁ-দৃষ্টান্ত রয়েছে যা তাত্পর্যপূর্ণভাবে বৃদ্ধি পায় এবং যদি এল দ্রুতগতিতে অনেক হ্যাঁ-দৃষ্টান্ত সহ একটি ভাষা হয় তবে এটি একটি বিরল ভাষার পি-সমরূপ হতে পারে না, কারণ এর হ্যাঁ-দৃষ্টান্তগুলিকে এক-থেকে-এক ম্যাপিং হওয়ার জন্য বহুপদী দীর্ঘতার চেয়ে বেশি স্ট্রিংয়ে ম্যাপ করতে হবে। বিরল এন. পি-সম্পূর্ণ ভাষাগুলির অস্তিত্বের পরিবর্তে বোঝায় যে পি ষ্ণ এন. পি, কারণ যদি পি = এন. পি হয় তবে পি-এর প্রতিটি অ-তুচ্ছ ভাষা (কিছু বিরল সহ, যেমন বাইনারি স্ট্রিংয়ের ভাষা যার সমস্ত বিট শূন্য) এন. পি-সম্পূর্ণ হবে। 1982 সালে, স্টিভ মাহানি তাঁর প্রমাণ প্রকাশ করেন যে বিরল এন. পি-সম্পূর্ণ ভাষাগুলির অস্তিত্বহীনতা (এন. পি-সম্পূর্ণতা সহ বহু-এক হ্রাস ব্যবহার করে মানক উপায়ে সংজ্ঞায়িত) আসলে এই বিবৃতির সমতুল্য যে পি ষ্ণ এন. পি; এটি মাহানির উপপাদ্য। এমনকি টুরিং হ্রাস ব্যবহার করে এনপি-সম্পূর্ণতার একটি শিথিল সংজ্ঞার ক্ষেত্রেও, একটি বিরল এনপি-সম্পূর্ণ ভাষার অস্তিত্ব বহুপদী শ্রেণিবিন্যাসের অপ্রত্যাশিত পতনকে বোঝায়। অনুমানের প্রমাণ হিসাবে, প্রমাণ দেখায় যে একটি সীমাবদ্ধ ধরনের হ্রাস সহ একটি অনুরূপ অনুমান সত্যঃ এসি0 বহু-এক হ্রাসের অধীনে এনপি-র জন্য সম্পূর্ণ প্রতিটি দুটি ভাষার একটি এসি0 সমরূপতা রয়েছে। এটি দেখায় যে, যদি একমুখী ফাংশন বিদ্যমান থাকে যা সমস্ত ইনপুটগুলিতে বহুপদী সময়ে উল্টানো যায় না, তবে যদি এই ধরনের প্রতিটি ফাংশনে ইনপুটগুলির একটি ছোট কিন্তু ঘন উপসেট থাকে যার উপর এটি পি/পলিতে উল্টানো যেতে পারে (যেমন এই ধরনের পরিচিত ফাংশনের জন্য সত্য) তবে প্রতিটি দুটি এনপি-সম্পূর্ণ ভাষার একটি পি/পলি আইসোমরফিজম থাকে। এবং একটি ওরাকল মেশিন মডেল খুঁজে পেয়েছেন যেখানে আইসোমরফিজম অনুমানের অনুরূপ সত্য। অনুমানের বিরুদ্ধে প্রমাণ এবং দ্বারা সরবরাহ করা হয়েছিল। জোসেফ এবং ইয়ং এনপি-সম্পূর্ণ সমস্যার একটি শ্রেণী, কে-ক্রিয়েটিভ সেট চালু করেছিলেন, যার জন্য স্ট্যান্ডার্ড এনপি-সম্পূর্ণ সমস্যার কোনও পি-আইসোমরফিজম জানা যায় না। কুর্তজ এবং অন্যান্য। দেখিয়েছেন যে ওরাকল মেশিন মডেলগুলিতে একটি র্যান্ডম ওরাকলে প্রবেশাধিকার দেওয়া হয়েছে, অনুমানের এনালগটি সত্য নয়ঃ যদি এ একটি র্যান্ডম ওরাকল হয়, তবে এনপিএ-র জন্য সম্পূর্ণ সমস্ত সেটের পিএ-তে আইসোমরফিজম থাকে না। র্যান্ডম ওরাকলগুলি সাধারণত ক্রিপ্টোগ্রাফি তত্ত্বে ক্রিপ্টোগ্রাফিক হ্যাশ ফাংশন মডেল করতে ব্যবহৃত হয় যা গণনামূলকভাবে র্যান্ডম থেকে আলাদা করা যায় না এবং কার্টজ এট আল-এর নির্মাণ। ওরাকলের জায়গায় এই ধরনের ফাংশন দিয়ে করা যেতে পারে। এই কারণে, অন্যদের মধ্যে, বারম্যান-হার্টম্যানিস আইসোমরফিজম অনুমানটি অনেক জটিলতা তাত্ত্বিকদের দ্বারা মিথ্যা বলে মনে করা হয়। তথ্যসূত্র কাঠামোগত জটিলতা তত্ত্ব কম্পিউটার বিজ্ঞানে অমীমাংসিত সমস্যার অনুমান গণিতে অমীমাংসিত সমস্যা