ریاضیات با کسی شوخی ندارد و اما و اگر نمی‌شناسد. اگر تحت فرضیاتی، مساله‌ای اثبات شد، دیگر آن مساله، تحت همان فرضیات قابل ابطال نیست. ما در ریاضیات و به طور مشخص، در علوم کامپیوتر، شاخه‌ای داریم که به عنوان نظریه‌ی پیچیدگی یا Complexity Theory شناخته می‌شود. در این شاخه، ما می‌خواهیم ببینیم که محاسبات برای حل یک مساله، ذاتا چقدر می‌تواند پیچیده باشد. مثلا فرض کنید که یک میلیون عدد داریم و می‌خواهیم الگوریتمی پیدا کنیم که طبق این الگوریتم، ببینیم که آیا همه‌ی این اعداد، از هم متمایز هستند یا خیر؟ یعنی باید ببینیم که آیا در بین اعداد، هیچ دو عدد یکسانی وجود دارد یا نه؟
به این مساله، مساله‌ی تمایز المان‌ها یا Elements Distinctness Problem گفته می‌شود.
یک الگوریتم می‌تواند این باشد که من از اولین عدد شروع کنم. بعد عدد دوم را با آن مقایسه کنم. اگر عدد دوم با عدد اول یکی بود، سریعا می‌گویم که همه‌ی اعداد این مجموعه از هم متمایز نیستند. پیدا کردن یک جفت عدد یکسان کافی‌ست که من بگویم همگی این اعداد از هم متمایز نیستند. اما اگر عدد اول و عدد دوم یکسان نبودند، من باید بروم و عدد سوم را با عدد اول و عدد دوم مقایسه کنم. و دوباره این فرآیند را تکرار کنم. من باید یک میلیون عدد را به همین شکل چک کنم. پس من حداقل یک میلیون مرحله دارم. از طرف دیگر، من هر بار باید عدد جدید را با تمام اعداد قبلی مقایسه کنم تا ببینم که آیا این عدد جدید، با بقیه‌ی اعداد یکسان است یا خیر، که این مقایسه هم پیچیدگی خودش را دارد. حالا در این شاخه از ریاضیات، ریاضی‌دانان اثبات کرده‌اند که این مساله چقدر از نظر محاسباتی پیچیده است.
ریاضی‌دانان اثبات کرده‌اند که اگر لیست شما n عدد داشته باشد، هر الگوریتمی پیدا کنید، پیچیدگی محاسباتی این مساله نمی‌تواند از n ضربدر لگاریتم n، کمتر شود. یعنی اگر صد عدد داشته باشید، هیچ الگوریتمی نمی‌تواند این مساله را در کمتر از هزار مرحله حل کند. این مقدار از پیچیدگی محاسباتی، ذاتی این مساله است و ربطی به الگوریتم ما ندارد. اینجاست که می‌گوییم ریاضیات با کسی شوخی ندارد.
فرض کنید فردا شخصی بیاید و با الگوریتمی بگوید که من به جای اینکه از یک طرف لیست، مقایسه ام را شروع کنم، اول عدد اول و عدد آخر لیست را مقایسه می‌کنم. آن دیگری می‌گوید من از ماشین تورینگ چندنواره استفاده می‌کنم. آن دیگری می‌گوید من به جای کامپیوتر از سوپرکامپیوتر استفاده می‌کنم. شخص دیگری سر و کله‌اش پیدا می‌شود و می‌گوید من این مساله را با کامپیوترهای کوانتومی و با الگوریتم‌های کوانتومی حل خواهم کرد. اصلا هیچ فرقی نمی‌کند. حد پایین پیچیدگی این مساله، قبلا اثبات شده است. یعنی ما و شما هرکاری بکنیم و هرچقدر خلاقیت به خرج دهیم و از هر نوع هوشی بهره بگیریم، این مساله را نمی‌توان با پیچیدگی کمتری حل کرد. این مثل حساب دو دو تا چهارتاست.
اگر روزی کسی به سراغتان آمد و گفت که من این مساله را در n مرحله حل می‌کنم، شما با خیال راحت می‌توانید حرفش را قبول نکنید. در بهترین حالت، او پیچیدگی الگوریتمش را اشتباه حساب کرده است. چون حد پایین این مساله اثبات شده است. البته نزدیک شدن به همان حد پایین هم خودش شاهکاری است.
تصویر فوق: در بازی GTA، شما نمی‌توانستید از مرزهای شهر خارج شوید، حالا با موتور، ماشین، پیاده، قایق یا هرچیزی. در نوجوانی، بخش زیادی از زمان ما برای این بازی، صرف این شد که از این مرزها عبور کنیم اما هیچوقت موفق نمی‌شدیم.
– اَبا اِباد