কম্পিউটিং ও এআই · পরীক্ষণ
সীমাটি হারাও
একটি নেটওয়ার্ক, এমন একদল মানুষ যাঁরা সবাই একে অপরকে চেনেন, ম্যাট্রিক্স গুণের মধ্য দিয়ে 1985 সালের একটি শর্টকাট, আর কয়েক দশক ধরে টিকে থাকা একটি অনুকল্প। k-ক্লিক অনুকল্পের অবসান নিয়ে চারটি প্রশ্ন, প্রাথমিক থেকে উন্নত পর্যন্ত।
1 · কী প্রমাণিত হলো, বলো
প্রাথমিক
k-ক্লিক অনুকল্প নিয়ে নিবন্ধটি কী দেখায়?
2 · 1985 সালের খরচ হিসাব করো
নেশেত্রিল–পোলিয়াক পদ্ধতি প্রায় n^(ωk/3) ধাপে একটি k-ক্লিক খুঁজে পায়। ধরো k = 9 আর ω = 2, ω-এর সম্ভাব্য সর্বনিম্ন মান।
মধ্যবর্তী
1985 সালের পদ্ধতি n-এর কোন সূচক দেয়?
3 · “এমনকি ω = 2 হলেও” ব্যাখ্যা করো
অনুকল্পটি n^(ωk/3) খরচের পূর্বাভাস দেয়। ω-এর সঠিক মান অজানা: এটি অন্তত 2, আর নিবন্ধটি 9/4-এর একটি ঊর্ধ্বসীমার উল্লেখ করে।
উন্নত
নতুন সাশ্রয়টি ω যা-ই হোক, এমনকি ω = 2 হলেও, টিকে থাকে — এটা কেন গুরুত্বপূর্ণ?
4 · লাভটি অন্যত্র নিয়ে যাও
n বুলিয়ান চলরাশির ওপর Max-2-CSP, যার মধ্যে পড়ে Max-Cut আর Max-2-SAT, সমাধান হতো প্রায় 2^(ωn/3) ধাপে। চলরাশিগুলোকে নয়টি দলে ভাগ করো, তাহলে প্রতিটি দলের মান-নির্ধারণ হয়ে ওঠে একটি ভারযুক্ত নয়-ক্লিক সমস্যার একটি শীর্ষবিন্দু।
উন্নত
নতুন ক্লিক অ্যালগরিদম এই সমস্যাগুলোর জন্য কী দেয়?
সীমা হার মানল
—