بازی کندی کراش پیچیده‌تر از آن است که فکر می‌کنید

۳-SAT عملیاتی در منطق است که بررسی می‌کند آیا یک مجموعه از سری‌های مرتبط یا الحاقی از عبارت‌های منطقی درست هستند یا منجر به تناقض می‌شوند. نمونه‌ای از چنین الحاقی عبارت‌ است از: x ∧ ¬x.. در نگاه اول، این عبارت به نظر پیچیده می‌آید، اما با دانستن معنی ∧ و ¬ (نوعی علامت سلب) می‌توانید به راحتی آن را تفسیر کنید؛ بنابراین این عبارت را می‌توان به این صورت تفسیر کرد: x و درعین‌حال غیر x. عملیات این عبارت تخصیص مقدار «درست» یا «غلط» به متغیر x است، به‌طوری‌که عبارت کلی درست باشد (به بیان دیگر منجر به تناقض نشود).

در مثال فوق، این نتیجه غیر ممکن است زیرا در صورتی که x درست باشد (x=true)، به دو عبارت درست و در عین حال غیردرست می‌رسید و درصورتی‌که x=false باشد، به دو عبارت غلط و غیرغلط به صورت همزمان خواهید رسید. هیچ‌کدام از این عبارت‌ها معنایی ندارند؛ زیرا یک چیز نمی‌تواند همزمان غلط و درست باشد. در نتیجه الحاق عبارت‌ها صدق نمی‌کنند.

مسئله‌‌های ۳-SAT شامل عبارت‌های زنجیره‌ای هستند که هر کدام به صورت مستقیم سه متغیر را به شکل (a1 ∨ b1 ∨ c1) ∧ (a2 ∨ b2 ∨ c2) ∧ … ∧ (an ∨ bn ∨ cn) به یکدیگر وصل می‌کنند. در اینجا V نشان‌دهنده‌ی «یا» است. کامپیوتر باید برای تخصیص مقدارهای درستی به متغیرها تلاش کند به‌طوری‌که عبارت کلی، درست باشد. همان‌طور که پیداست این عملیات از نوع NP سخت است. با افزایش طول عملیات، زمان محاسباتی هم به‌صورت نمایی افزایش می‌یابد.

والش در مرحله‌ی بعد باید نشان می‌داد هر مسئله‌ی ۳-SAT را می‌توان در کندی‌کراش نمایش داد و حل کندی‌کراش به صورت خودکار به حل مسئله‌ی مرتبط ۳-SAT می‌انجامد. او برای رسیدن به این هدف، آرایش‌های آب‌نباتی بازی کندی‌کراش را با متغیرها و اتصال‌های منطقی در مسئله‌ی ۳-SAT تطبیق داد به گونه‌ای که یک الگوی مشخصی از آب‌نبات‌ها نمایشگر یک متغیر باشد. به این ترتیب، او توانست ثابت کند هر عبارت منطقی به شکل ۳-SAT را می‌توان با توزیع مناسبی از آب‌نبات‌ها در کندی‌کراش نمایش داد.

مسئله فوق به این صورت کار می‌کند: وقتی بازیکنی جابه‌جایی مشخصی را اجرا کند، والش آن را به صورت تخصیص یک مقدار درست به یک متغیر تفسیر می‌کند. برای مثال، متغیر ۱ اشتباه است. هر جابه‌جایی می‌تواند زمین بازی را تغییر دهد. علاوه بر این، می‌تواند زنجیره‌ای با سه آب‌نبات ایجاد کند که به صورت آنی ناپدید می‌شوند و به دیگر آب‌نبات‌ها اجازه می‌دهد از صفحه پائین بروند.

اگر تعداد جابه‌جایی‌ها متناظر با متغیرهای مسئله‌ی ۳-SAT باشد، می‌توان از باقی‌مانده‌ی آب‌نبات‌های روی صفحه حدس زد که عبارت ۳-SAT درست یا غلط است. برای مثال اگر مربع در سطر سوم و ستون دوم حاوی یک آب‌نبات لیمویی زرد پس از تمام جابه‌جایی‌ها باشد، متناظر با عبارت «درست» است. والش آب‌نبات زمین بازی را به گونه‌ای توزیع کرد که آب‌نبات لیمویی زرد تنها در صورتی روی زمین بازی قرار بگیرد که حداقل تعداد سه زنجیره‌ی آب‌نباتی شکل گرفته باشند.

به این ترتیب والش توانست در مارس ۲۰۱۴ ثابت کند که کندی‌کراش از نوع NP سخت است و می‌توان گفت پیچیدگی بالایی از دیدگاه ریاضی دارد. این پیچیدگی می‌تواند اطمینان دهد که بالاخره در مرحله‌ای از کندی‌کراش شکست می‌خورید با این‌حال همان‌گونه که والش می‌گوید، این بازی جذابیت‌هایی دارد: «این ویژگی می‌تواند بخشی از خاصیت اعتیادآور بازی کندی‌کراش باشد، اگر حل آن راحت بود، به این اندازه جذاب نمی‌شد.»