هذه قضايا معروفة وقديمة في نظرية التعقيد الحسابي computational complexity ،

ومسألة البائع المسافر Traveling Salesman من أشهر المسائل التي تسمى NP-Hard Problems ..

ما يعنيه هذا .. لنفرض أن هناك مسألة معينة كمسألة البائع فيها عدد n ، المطلوب إيجاد خوارزمية معينة algorithm تقوم بحل المسألة لقيمة معينة n ..
كمية الحسابات التي تحتاجها الخوارزمية تمثل كدالة function بدلالة n . طبعاً المهم هنا كيفية نمو هذه الدالة بزيادة n . هل تزيد بمعدل حدودية in the order of a polynomial أو بمعدل أسي exponential growth .. أو إلخ .

يمكن حل المسألة بسرعة إذا كانت هناك خوارزمية تعقيدها يكون بمعدل حدودية .. وتسمى هذه المسائل P problems ، وعادة يقال أنها مسائل سهلة .

أما إذا لم يمكن إيجاد مثل هذه الخوارزمية بالمعدل المطلوب فإنها تسمى Non-deterministic polynomial .. ويرمز لها NP problems .
ففي حالة مسائل NP فإن عدد الدورات iterations لحل المسألة يزيد بزيادة n بشكل خرافي مما يشكل عبئاً على الكمبيوترات لحلها .

الطريف في الموضوع أنها لحد الآن لم يثبت أحد أنه يستحيل إيجاد خوارزمية حدودية لمسائل NP .. وتبقى مسألة مفتوحة هل NP=P أم لا ؟ مع أن معظم الباحثين يعتقدون بعدم تساويهما .


دعك من كل هذا .. جرب إيجاد معكوس مصفوفة بحجم متزايد .. إبدأ من 5000 وتجد أن الكمبيوتر المسكين يعاني أشد العناء .