كتب نظرية التعقيد الحاسوبية
اذا لم تجد ما تبحث عنه يمكنك استخدام كلمات أكثر دقة.
نظرية التعقيد الحاسوبية (معلومة)
لا تهتم نظرية التعقيد فقط فيما إذا كانت مسألة ما قابلة للحل أم لا على الحاسوب، لكنها تهتم أيضًا بالكفاءة التي يمكن حل المسألة بها. هناك مفهومان رئيسيان يؤخذان بعين الاعتبار هما: التعقيد الزمني والتعقيد المكاني، واللذان يشيران على التتالي إلى عدد الخطوات التي يتطلبها إجراء الحوسبة، وكمية الذاكرة المطلوبة لإجراء هذه الحوسبة.
لتحليل كمية الزمن والمكان الذي تتطلبه خوارزمية ما، يعبر علماء الحاسوب عن الزمن والمكان المطلوب لحل المسألة على أنه تابع لحجم مدخلات المسألة. على سبيل المثال، إيجاد رقم محدد في قائمة طويلة من الأرقام يصبح أصعب كلما كانت قائمة الأرقام أكبر. إذا قلنا إن هناك ن(n) رقم في قائمة ما، في حال كانت القائمة غير مرتبة أو غير مفهرسة بأي شكل، سنضطر إلى المقارنة مع كل رقم من أجل إيجاد الرقم الذي نبحث عنه. لذلك نقول إنه من أجل حل هذه المسألة، يحتاج الحاسوب لإجراء مجموعة من الخطوات تزداد خطيًا مع ازدياد حجم المسألة.
لتبسيط المسألة اعتمد علماء الحاسوب على ما يسمى رمز O الكبير الذي يسمح بمقارنة التوابع بطريقة تؤكد أنه يمكننا عدم أخذ جوانب محددة من بناء الآلة بعين الاعتبار، لكن بدلًا من ذلك نتبع الأسلوب المقارب فقط مع ازدياد حجم المسائل. إذّا في مثالنا السابق يمكن أن نقول إن المسألة تتطلب O(n) أو ن خطوة لحلها.
ربما تكون أهم مسألة مفتوحة في علوم الحاسب هي مسألة فيما إذا كان صف معين من المسائل التي يرمز لها NP (أي كثير حدود غير قطعي) قابلة للحل بكفاءة. نوقشت تلك الفكرة بشكل أكبر في صفوف التعقيد P (أي كثير حدود) وصفوف NP (أي كثير حدود غير قطعي)، وتعتبر مسألة كثير حدود وكثير حدود غير قطعي (P=NP?) واحدة من سبع مسائل جوائز الألفية، وصرح عنها معهد كلاي للرياضيات في عام 2000. طرح وصف المسألة، الفائز بجائزة تورنغ، ستيفن كوك.
