نظرية التعقيد الحسابي

مسائل جوائز الألفية
نظرية التعقيد
حدسية هودج
حدسية پوانكاريه
فرضية ريمان
وجود يانگ-ميلز وفجوة الكتلة
معادلات ناڤييه-ستوكس
حدسية بيرش وسوينرتون-داير
عدل

نظرية التعقيد احدى اجزاء نظرية الحوسبة و تتعامل مع الموارد المطلوبة في عملية الحوسبة . أكثر هذه الموارد شيوعا هي الزمن (بمعنى كم من الخطوات أو ما يقابلها من الوقت يلزم لحل المسألة ) و المكان (بمعنى ما حجم الذاكرة اللازمة لحل المسألة) ، يمكن ان يدخل بالاعتبار موارد أخرى ، مثل : كم عدد المعالجات المتوازية اللازمة لإنجاز الحساب باستخدام برمجة متوازية .

تختلف نظرية التعقيد عن نظرية الحسوبية في أن نظرية الحسوبية تدرس فيما إذا كانت المسألة قابلة للحساب ام لا بشكل مطلق ، اما نظرية التعقيد فتدرس كيفية إنجاز الحسابات بكفاءة و سرعة .

 تعاريف

في المعلومياتة تصنف المشاكل حسب صعوبة الحل, في هذه الحالة المقياس المستعمل هو الوقت و المساحة.

لإيجاد حلول للمشاكل الرياضية يتم اللجوء إلى الخوارزميات, إلا أن هناك مشاكل لها خوارزميات تحتاج لوقت كبير جدا لتعطي الحل, في حين هناك مشاكل أخرى يتم حلها بسهولة.

 الوقت و الزمن

من المعلوم أن معظم المشاكل يتم محاولة حلها باستعمال الحاسوب, و مع التطور التكنولوجي تتطور سرعة الأداء و يصبح الحاسوب قادرا على إجراء عمليات أكثر تعقيدا, لهذا وجب تحديد تعريف مستقل عن التكنولوجيا, مرتبط فقط بالخوارزميات, فمثلا إذا أخدنا عددين كل منهما مكون من 100 رقم, فإجراء عملية الجمع و الضرب بالحاسوب ستكون تقريبا آنية, فالمستعمل لن يشعر بأي فارق زمني.

إذن نعرف الزمن هنا على أنه عدد العمليات الأولية التي يحتاجها برنامج (خوارزمية) لإجراء العمليات.

 مشاكل حاسوبية

A traveling salesman tour through 14 German cities

 المشاكل الحدودية المحددة

هناك مشاكل سهلة الحل, حيث يتم إيجاد حل لها في وقت وجيز. فمثلا ترتيب مجموعة أعداد من الأصغر إلى الأكبر يتم في وقت قصير, و العلاقة الموجودة بين عدد عناصر المجموعة و الوقت الذي يستغرقه الحاسوب باستعمال خوارزميات الترتيب يعبر عنها بدالة حدودية.

عادة ما يرمز للمشاكل الحدودية المحددة ب: P

أمثلة:

1. جداء عددين.
2. القاسم المشترك لعددين.
3. معرفة هل عدد أولي أم لا.

 المشاكل الحدودية غير المحددة

هناك مشاكل صعبة الحل, حيث يتم إيجاد حل لها في وقت جد جد طويل. فمثلا تفكيك عدد إلى جداء أعداد أولية يحتاج إلى وقت طويل كلما كبر العدد, و العلاقة الموجودة بين عدد عناصر المجموعة و الوقت الذي يستغرقه الحاسوب باستعمال خوارزميات الترتيب يعبر عنها بدالة أسية في أغلب الأحيان.

كما أنه إذا كان من الصعب إيجاد الحل, فإنه من السهل التأكد من صحة أو خطأ الجواب, فعملية التأكد و التحقق من الجواب تجرى في وقت حدودي.

عادة ما يرمز للمشاكل الحدودية غير المحددة ب: NP

أمثلة:

1. مشكلة تلوين المخطط.
2. مشكلة التفكيك إلى جداء عوامل أولية.
3. مشكلة المخطط الكامل ضمن مخطط.

 المشاكل الحدودية المحددة مقابل المشاكل الحدودية غير المحددة

من السهل ملاحظة أن المشاكل المحددة هي ضمن المشاكل غير المحددة, لكن المشكلة العظمى والتي لم يتمكن من الجواب عنها علماء المعلوميات مند سنة 1971 إلى الآن هو هل هناك تساو أو اختلاف بين الصنفين؟ و أول من يتمكن من الإجابة على هذا السؤال يأخد جائزة مالية قدرها 100000$.

 الاختصار

ليكن P و Q مشكلتين من صنف C)Cاعتباطي), نقول أن المشكل P يُختصر إلى المشكل Q, إذا وُجدت دالة f تحول كل هيئة من P إلى هيئة من Q. نقول أن حل المشكل Q يؤدي إلى حل المشكل P. أو كل خوارزمية تحل Q, تحل P.

 تعريف

نقول أن المشكل P, مشكل حدودي غير محدد كامل NP-complet إذا كان أصعب من جميع المشاكل المنتمية إلى صنف المشاكل الحدودية غير المحددة NP. أو كان هناك اختصار حدودي من أي مشكل من صنف NP إلى المشكل P.

 مبرهنة كوك و ليفين

الاكتفاء (معروف ب SAT) مشكل كامل .

 مشاكل كاملة أخرى

1. مشكلة تلوين المخطط.
2. مشكلة التفكيك إلى جداء عوامل أولية.
3. مشكلة المخطط الكامل ضمن مخطط.
4. مشكلة الرحالة التاجر.

 خاصية مهمة للمشاكل الكاملة

وجود خوارزمية حدودية لأي مشكل كامل يعني أن P=NP. و عكسيا عدم وجود خوارزمية حدودية لأي مشكل كامل يعني أن P#NP.

 لاندو

ترميز لاندو خاص بالمشاكل ويرمز له ب O (الحرف اللاتيني), يقدم فكرة عن سرعة دالة تتزايد أو تتناقص.

مثلا, عند تحليل خوارزمية ما, يمكن حساب عدد العمليات أو عدد المراحل اللازمة للحل, و قد نجد مثلا: T(n) = 4 n² - 2 n + 2. بالنسبة للبعد n.

هنا يمكن اهمال الثوابت و نقول أن T(n) تتزايد من الرتبة أو الدرجة n², و نكتب: >T(n) = O(n²).

ترميز		التعقيد
O(1)		ثابت
O(log(n))		لوغاريثمي
O(n log(n))		لوغاريثمي-خطي
O((log(n))c)		لوغاريثمي-متعدد
O(n)		خطي
O(n2)		رباعي
O(nc)		حدودي
O(cn)		أسي
O(n!)		عاملي

 التاريخ

An early example of algorithm complexity analysis is the running time analysis of the Euclidean algorithm done by Gabriel Lamé in 1844.

Before the actual research explicitly devoted to the complexity of algorithmic problems started off, numerous foundations were laid out by various researchers. Most influential among these was the definition of Turing machines by Alan Turing in 1936, which turned out to be a very robust and flexible simplification of a computer.

The beginning of systematic studies in computational complexity is attributed to the seminal 1965 paper "On the Computational Complexity of Algorithms" by Juris Hartmanis and Richard E. Stearns, which laid out the definitions of time complexity and space complexity, and proved the hierarchy theorems. In addition, in 1965 Edmonds suggested to consider a "good" algorithm to be one with running time bounded by a polynomial of the input size.

Earlier papers studying problems solvable by Turing machines with specific bounded resources include John Myhill's definition of linear bounded automata (Myhill 1960), Raymond Smullyan's study of rudimentary sets (1961), as well as Hisao Yamada's paper on real-time computations (1962). Somewhat earlier, Boris Trakhtenbrot (1956), a pioneer in the field from the USSR, studied another specific complexity measure. As he remembers:

However, [my] initial interest [in automata theory] was increasingly set aside in favor of computational complexity, an exciting fusion of combinatorial methods, inherited from switching theory, with the conceptual arsenal of the theory of algorithms. These ideas had occurred to me earlier in 1955 when I coined the term "signalizing function", which is nowadays commonly known as "complexity measure".

In 1967, Manuel Blum formulated a set of axioms (now known as Blum axioms) specifying desirable properties of complexity measures on the set of computable functions and proved an important result, the so-called speed-up theorem. The field began to flourish in 1971 when Stephen Cook and Leonid Levin proved the existence of practically relevant problems that are NP-complete. In 1972, Richard Karp took this idea a leap forward with his landmark paper, "Reducibility Among Combinatorial Problems", in which he showed that 21 diverse combinatorial and graph theoretical problems, each infamous for its computational intractability, are NP-complete.

 انظر أيضاً

• Computational complexity
• Descriptive complexity theory
• Game complexity
• Leaf language
• Limits of computation
• List of complexity classes
• List of computability and complexity topics
• List of unsolved problems in computer science
• Parameterized complexity
• Proof complexity
• Quantum complexity theory
• Structural complexity theory
• Transcomputational problem
• Computational complexity of mathematical operations

 أعمال في التعقيد

• Wuppuluri, Shyam; Doria, Francisco A., eds. (2020), Unravelling Complexity: The Life and Work of Gregory Chaitin, World Scientific, doi:10.1142/11270, ISBN 978-981-12-0006-9, https://www.worldscientific.com/worldscibooks/10.1142/11270 

 المراجع

 الكتب الدراسية

• Arora, Sanjeev; Barak, Boaz (2009), Computational Complexity: A Modern Approach, Cambridge University Press, ISBN 978-0-521-42426-4, http://www.cs.princeton.edu/theory/complexity/ 
• Downey, Rod; Fellows, Michael (1999), Parameterized complexity, Monographs in Computer Science, Berlin, New York: Springer-Verlag, ISBN 9780387948836 
• Du, Ding-Zhu; Ko, Ker-I (2000), Theory of Computational Complexity, John Wiley & Sons, ISBN 978-0-471-34506-0 
• قالب:Garey-Johnson
• Goldreich, Oded (2008), Computational Complexity: A Conceptual Perspective, Cambridge University Press, http://www.wisdom.weizmann.ac.il/~oded/cc-book.html 
• van Leeuwen, Jan, ed. (1990), Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, ISBN 978-0-444-88071-0 
• Papadimitriou, Christos (1994), Computational Complexity (1st ed.), Addison Wesley, ISBN 978-0-201-53082-7 
• Sipser, Michael (2006), Introduction to the Theory of Computation (2nd ed.), USA: Thomson Course Technology, ISBN 978-0-534-95097-2 

 مسح

• Khalil, Hatem; Ulery, Dana (1976), "A review of current studies on complexity of algorithms for partial differential equations", Proceedings of the annual conference on – ACM 76, pp. 197–201, doi:10.1145/800191.805573, ISBN 9781450374897, http://portal.acm.org/citation.cfm?id=800191.805573 
• Cook, Stephen (1983), "An overview of computational complexity", Communications of the ACM 26 (6): 400–408, doi:10.1145/358141.358144, ISSN 0001-0782 
• Fortnow, Lance; Homer, Steven (2003), "A Short History of Computational Complexity", Bulletin of the EATCS 80: 95–133, http://people.cs.uchicago.edu/~fortnow/papers/history.pdf 
• Mertens, Stephan (2002), "Computational Complexity for Physicists", Computing in Science & Engineering 4 (3): 31–47, doi:10.1109/5992.998639, ISSN 1521-9615, Bibcode: 2002CSE.....4c..31M 

 وصلات خارجية

ابحث عن feasible في
قاموس المعرفة.

• The Complexity Zoo
• Hazewinkel, Michiel, ed. (2001), "Computational complexity classes", Encyclopaedia of Mathematics, Kluwer Academic Publishers, ISBN 978-1556080104 
• Scott Aaronson: Why Philosophers Should Care About Computational Complexity