اليوم هو السبت أكتوبر 25, 2014 1:09 pm
حجم الخط

الساحة العلميّة

تغذية نسخة للطباعة

أهم 7 مسائل رياضية غير محلولة في هذا العصر

غرفة لنقاش المواضيع العلمية: الطبيعة، نشأة الكون، التطور، فيزياء، فلك، كيمياء، أحياء....الخ

أهم 7 مسائل رياضية غير محلولة في هذا العصر

رقم المشاركة:#1  مشاركةبواسطة المعتزلي الهاشمي » الثلاثاء ديسمبر 12, 2006 1:57 pm

تحية للجميع

في المجتمع العلمي هناك 7 مشاكل رياضية تعتبر هي الأعقد والأصعب والتي لم يستطع أحد حلها حتى الآن
وقد خصصت جائزة قدرها مليون دولار لأي شخص يجد حل لأي مسألة من المسائل السبعة من قبل معهد cmi للرباضيات

الوصول لحل لأي مسألة من المسائل السبعة سيكون له أهمية بالغة على تقدم العلم في مجالات عدة وعلى تقدم البشرية بشكل عام وهذا نظرا لأهمية هذة المسائل السبعة

المشاكل السبعة الرئيسية هي :

1.1 P versus NP
1.2 The Hodge conjecture
1.3 The Poincaré conjecture
1.4 The Riemann hypothesis
1.5 Yang-Mills existence and mass gap
1.6 Navier-Stokes existence and smoothness
1.7 The Birch and Swinnerton-Dyer conjecture

وتجدون تفصيل عنها في ويكيبيديا على الرابط التالي:
http://en.wikipedia.org/wiki/Clay_Mathematics_Institute

بصراحة أنا قرأت عنها ولم أفهم شئ :97:

وقد سمعت أن شابا روسيا قبل شهرين توصل لحل لإحدى هذة المسائل وعرضت عليه جائزة فيلدز ولكنه رفضها ومتوقع أن يحصل على مليون دولار كونه قام بحل إحدى المشاكل السبعة الأساسية في الرياضيات
وقد قرأت أن حل هذة المسألة سيكون له دور كبير في علم الكون وفي فهم طبولوجيا وتركيب الكون !!

الآن

نرجوا ممن لديه معرفة أن يعطينا لمحة مبسطة عن هذة المسائل ماهي ؟ وما مجالها؟ ولماذا لم يتمكن أحد من حلها حتى الآن ؟ وما هي المنافع التي ستحدث في حال حل كل منها ؟

نرجوا أن يكون شرحا مبسطا ومستفيضا لغير المتخصصين في الرياضيات

وشكرا
لا تأخذ المعرفة إلا بدليل
ولا تنقض إلا بدليل
صورة العضو الشخصية
المعتزلي الهاشمي
مشترك ذهبي
 
مشاركات: 128
اشترك في: الأحد يناير 22, 2006 12:56 am
الجنس: غير محدد

رقم المشاركة:#2  مشاركةبواسطة _muslim_ » الثلاثاء ديسمبر 12, 2006 8:20 pm

سأحاول أن أجيبك على النقطة الأولى NP vs. P ..

دعنا نتناول المشكلة من البداية ..
في عام 1900 طرح الرياضي الأشهر ديفيد هلبرت David Hilbert مسائله الثلاث و عشرين التي اعتبرها أهم معضلات رياضية تنتظر القرن العشرين .. تضمنت المسألة العاشرة تساؤلا عن معضلة رياضية معينة و هل توجد طريقة رياضية لحلها أم لا ..

لا تعنينا مسألة هلبرت العاشرة الآن، فقد تم الفصل فيها منذ زمن، و لكن ما يعنينا الآن هو ما رآه العلماء فيها، من أن هذه هي المرة الأولى التي يتساءل فيها عالم رياضي، لا عن حل مسألة رياضية، بل عن قابلية المسألة الرياضية للحل أساسا!!
فتح هذه التساؤل نقاشا فلسفيا عن قوة الرياضيات، و ما هي حدودها ..

ثم، و في الثلاثينيات من هذا القرن، وضع العالم الانجليزي (آلان تورنغ) تصميما نظريا، لماكينة يمكنها حل أي مسألة رياضية قابلة للحل .. و المقصود بذلك، أن الماكينة تمتلك نفس القوة الحسابية Computational Power للرياضيات .. سميت هذه الماكينة بماكينة تورنغ Turing Machine .. و هي مجرد نموذج رياضي Mathematical Model و ليست ماكينة حقيقية ..

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

إذا كان الأمر غامضا فلا تقلق .. يكفيك أن تمتلك إحساسا عاما بآلية عمل الماكينة ..

إن كل ما يمكن للحاسبات الآلية أن تفعله، حاليا أو مستقبلا، يمكن لماكينة تورنغ أن تفعله (مع فارق السرعة) .. لأن قوة أي حاسب آلي، أيا كانت، لن تتجاوز قوة الرياضيات أبدا (لا يستطيع الحاسب الآلي حل مسألة، دون أن تكون الرياضيات قادرة على حلها) ..
في الواقع، إن هذه الماكينة هي التعريف المجرد للرياضيات ..

تطور المفهوم بعد ذلك إلى اعتبار الكون كله، في انتقاله من حالة إلى أخرى، عبارة عن ماكينة تورنغ كبيرة .. فالوضع الحالي للكون يمثل الدخل input للماكينة، و الوضع القادم هو الخرج output، و قوانين الطبيعة هي التعليمات instructions .. مع استخدام أي أبجدية مناسبة ( الأعداد المركبة مثلا .. أو حتى الحروف اللاتينية) ..

فأي عملية ميكانيكية/رياضية/كيميائية في الكون يمكن تمثيلها بهذا الشكل .. و أصبحت ماكينة تورنغ نموذجا نظريا يستخدمه علماء الرياضيات لتحديد ما يمكن (و ما لا يمكن) تنفيذه بشكل آلي مبرمج مسبقا ..

فمثلا، تم إستخدامها لإثبات أن الرياضيات عاجزة عن إثبات جميع القوانين لحساب الضرب و الجمع .. وكذلك تم استخدامها لإثبات نظرية جودل Godel Incompleteness Theorem و التي تنص على أن أي نظام رياضي (يتضمن آلية للإثبات) لا يمكن إثبات جميع قوانينه.

صمم العلماء كذلك عدة نماذج رياضية، كلها تماثل ماكينة تورنغ في القوة الحسابية .. مثل حساب لامدا Lambda Calculus و ماكينة بوست Post Machines .. هذه النماذج أيضا يمكنها محاكاة أي عملية آلية (رياضية، ميكانيكية .. إلخ) .. لكن نموذج تورنغ ظل هو الأكثر شيوعا ..

أما القول بأن الكون كله عبارة عن ماكينة تورنغ كبيرة، فقد ظل أطروحة لا يمكن إثباتها .. فهل الكون كله فعلا يمكن تمثيله بعملية آلية محددة مسبقا deterministic؟
هذا التساؤل الفلسفي يخرج عن نطاق موضوعنا الآن ..

نعود إلى موضوعنا ..

عند استخدام ماكينة تورنغ (أو أي نموذج رياضي آخر) لحل معضلة رياضية، يمكننا من خلال تحليلنا للمعضلة، أن نحدد العدد الأقصى من العمليات التي ستحتاجها الماكينة لتنفيذ العملية المطلوبة بحيث تحل المسألة (تذكر أن أي ماكينة تورنغ تقوم بتحويل الدخل المعطى لها إلى خرج معين بناءا على تعليمات مسبقة) ..

مثلا .. لنفرض أننا بصدد ماكينة تورنغ تقوم بتحويل أي كلمة لاتينية إلى الكلمة ذاتها معكوسة ..
فتحول كلمة word إلى drow ..
هذه العملية يمكن تنفيذها بشكل آلي بناءا على تعليمات مسبقة .. التعليمات ستكون:
"قم بإعادة كتابة الدخل، بدءا من الحرف الأخير، و انتهاءا بالحرف الأول"

العدد الأقصى للعمليات التي تحتاجها الماكينة لتنفيذ عملية رياضية ما، هو ما يعرف بـالتعقيد الزمني للعملية Time Complexity .. هناك أنواع أخرى من التعقيد الحسابي Computational Complexity لكننا لن نخوض فيها الآن ..

لا يتم حساب هذا العدد على شكل عدد صحيح، و إنما على شكل دالة في حجم الدخل ..

في حالتنا هذه إذا كان حجم الدخل (عدد الحروف) يساوي n فإن عدد العمليات التي تقوم بها الماكينة هو n.s .. حيث أن s هو عدد العمليات التي تحتاجها الماكينة لكتابة حرف معين ..
القيمة s هي قيمة ثابتة لا نكترث بها عند دراسة المسألة نظريا .. و يكفي أن نقول أن التعقيد الزمني للعملية هو دالة متعددة الحدود من الدرجة الأولى first degree polynomial في حجم الدخل ..

مجموعة المسائل التي يمكن حلها على ماكينة تورنغ، بتعقيد زمني يساوي دالة متعددة الحدود من أي درجة .. هي ما نسميه P .. اختصارا لـPolynomial ..

إذا كنت لا تذكر الدوال المتعددة الحدود يمكنك مراجعة أي كتاب في مبادئ الجبر ..

بعض المسائل يكون تعقيدها الزمني على شكل دالة أسية exponential (ثابت مروفع لأس، حيث أن هذا الأس على شكل دالة متعددة الحدود في n ) ..
مثلا:
5 مرفوعا للأس 3n+4
أو ..
2 مرفوعا للأس n مرفوعا للأس 2
أي أن عدد العمليات التي تحتاجها ماكينة تورنغ (أو أي نموذج رياضي مماثل) لحل المسألة يساوي دالة أسية في حجم الدخل ..
طبعا دالة بهذا الشكل لابد أن "تنمو" بمعدل أسرع بكثير من دالة متعددة الحدود .. أي أنه كلما ازداد حجم الدخل، لمسألة ذات تعقيد زمني أسي، ازدادت العمليات المطلوبة لحساب الخرج، بمعدل أكبر بكثير من المسائل ذات التعقيد الزمني المتعدد الحدود ..

هذه النوعية من المسائل تمثل مشكلة رياضية .. تخيل في الحالة الأخيرة (2 مرفوعا للأس n مرفوعا للأس 2) ، إذا كان حجم الدخل 1000 فإن عدد العمليات المطلوبة لحل المسألة يساوي 2 ^1000 ^ 2 أي أننا نحتاج لعدة تريليونات من السنين لحل المسألة !!

هذه العائلة من المسائل تسمى EXPTIME ..

(ملحوظة .. من أشهر الأمثلة على هذه النوعية من المسائل، الشطرنج !! ونظرا لضخامة التعقيد الزمني لهذه اللعبة، تقوم أجهزة الحواسيب المخصصة للعب الشطرنج بعمليات "تقريبية" لحساب الحركة التي يجب القيام بها)

يمكننا أن نقول أن مجموعة المسائل P هي جزء صغير من المجموعة EXPTIME .. لأن المسألة التي يمكن حلها في عدد صغير من العمليات يمكن حلها أيضا في عدد أكبر من العمليات (عن طريق القيام بعمليات غير ضرورية) .. أما العكس فهو غير صحيح بالتأكيد ..

للأسف هناك الكثير من العمليات الهامة التي نحتاج لميكنتها لكنها تمتلك تعقيدا زمنيا أسيا exponential time complexity ..
بعض هذه المسائل قد ثبت رياضيا أنه لا يمكن حلها إلا بتعقيد زمني أسي، لا مفر من ذلك .. لكن البعض الآخر لم يثبت بعد، أي أننا لا نملك أن نؤكد بشكل قطعي أن المسألة لا يمكن حلها بتعقيد زمني متعدد الحدود، لكننا لم نعثر بعد على حل بهذه "السهولة" ..

أحد هذه المسائل (الغير محسومة) هي معضلة البائع الجائل Traveling Salesman Problem و يمكن أن تقرأ عنها بالتفصيل في الويكيبيديا:
إذا كان لدينا مجموعة من المدن، تربطها شبكة طرق، بحيث ترتبط كل مدينتين بطريق مباشر ذا طول معين .. فهل بإمكاننا تحديد مسار يتنقل به البائع الجوال بين المدن، بحيث يقطع أقل مسافة ممكنة، و يغطي جميع المدن، دون المرور على مدينة واحدة مرتين؟
الحل الوحيد المتاح (حاليا) يمتلك تعقيد زمني أسي، فكلما زاد عدد المدن مدينة واحدة، تضاعف عدد العمليات المطلوبة لحساب المسألة .. لكننا حتى الآن لم نثبت بشكل قطعي أنه لا يوجد حل ذو تعقيد زمني متعدد الحدود ..

تبين فيما بعد أن هذه المسائل (التي لم يحسم العلم أمرها بعد) يمكن حلها بتعقيد زمني متعدد الحدود، بشرط أن نعطي لماكينة تورنغ القدرة على القيام بعمليات مختلفة في آن واحد (تسمى هذه الماكينة بـ"ماكينة تورنغ الغير حتمية" Nondeterministic Turing Machine خلافا لماكينة تورنغ التقليدية التي صار اسمها "ماكينة تورنغ الحتمية" Deterministic Turing Machine) ..
و لذلك تسمى هذه المسائل "مسائل متعددة الحدود غير حتمية" Nondeterministic Polynomial و اختصارا نسميها NP ..

طبعا، نحن لا نتصور إمكانية تطبيق "ماكينة تورنغ الغير حتمية" في الواقع .. فنحن لا نتصور أن تتخذ الآلة وضعين مختلفين (أو عدة أوضاع مختلفة) في آن واحد .. أليس كذلك؟

(ملحوظة: ميكانيكا الكم قد أعطت بعض الأمل في ذلك، حيث يمكن لأي نظام كوانتي أن يتخذ عدة أوضاع في آن واحد، فيما يعرف باسم الحوسبة الكوانتية Quantum Computation .. لكن هذا المجال لم يزل طفلا يحبو، و للأسف تواجهه صعوبات جمة، ما يجعل العلماء يعتبرونه نموذجا غير واقعي في الوقت الحاضر)

و ختاما نصل إلى معنى سؤالنا P versus NP .. فالمعضلة التي لم تزل تؤرق العلماء هي: هل "ماكينة تورنغ الحتمية" تمتلك نفس القوة الحسابية لـ"ماكينة تورنغ الغير حتمية"؟ أو بعبارة أخرى هل يمكن للمسائل التي تنتمي للمجموعة NP أن تحل بتعقيد زمني متعدد الحدود على "ماكينة تورنغ الحتمية"؟

قد يتساءل البعض .. ما الذي يمكن أن يحدث لو أجبنا على هذا السؤال؟
الكثير في الواقع .. إن محاولة حل أي مسألة ذات تعقيد زمني أسي تعتبر محاولة غير مجدية .. خاصة إذا كان حجم الدخل كبيرا بما يكفي .. و لذلك يتم تصميم جميع نظم التشفير بحيث تكون عملية كسر الشفرة ذات تعقيد زمني أسي، و تكون بذلك أي محاولة لكسر الشفرة غير مجدية عمليا ..
لو تمكنا من حل المسائل التي تنتمي لـNP بتعقيد زمني متعدد الحدود على ماكينة تورنغ الحتمية (التي تمثل في قوتها الرياضية حواسيبنا الآلية) لانهارت كل نظم الأمان في البنوك و المؤسسات في لحظة واحدة!!

إن النتائج التي تعود علينا من حل مثل هذه المعضلة لا تعد و لا تحصى، بعضها مفيد و البعض الآخر كارثي، و إن كان الاعتقاد السائد بين العلماء هو أن الماكينتين (الحتمية و الغير حتمية) غير متساويتين غالبا .. أي أن المجموعة NP لا يمكن حلها كلها على "ماكينة تورنغ الحتمية" ..

أتمنى أن أكون قد أفدتك، و سأكون سعيدا بإجابة أي استيضاح منك عن الموضوع ..
و أترك الإجابة عن باقي الأسئلة لمن لديه دراية بها ..
"حتى لو كانت هناك نظرية موحدة للفيزياء، فهي مجرد معادلات. من الذي جعل لهذه المعادلات كونا لتنطبق عليه؟"
ستيفن هوكنج
صورة العضو الشخصية
_muslim_
مشترك فضِّي
 
مشاركات: 97
اشترك في: الأحد مارس 12, 2006 4:04 am
مكان: Canada
الجنس: غير محدد

رقم المشاركة:#3  مشاركةبواسطة المعتزلي الهاشمي » الأربعاء ديسمبر 13, 2006 11:50 am

ما شاء الله عليك أخ مسلم

على الرغم من إنني لا أفهم كثيرا في الرياضيات وغير متخصص بها ولكن من خلال شرحك تمكنت من فهم مقارب للموضوع

وكونك بدأت الشرح للمسألة الأولى p v np
فيهمني الإستيضاح منك عن المزيد من شرحك إلى أن ننتقل للمسألة الثانية

سأقوم بوضع فهمي للمسألة هنا وأرجو أن تصحح لي إن كان هناك خطأ

1- المسائل الرياضية على نوعين فإما إنها قابلة للحل من حيث المبدأ بعدد محدود من الخطوات وهي التي تنتمي لمجموعة P
أو غير قابلة للحل إلا بعدد هائل من الخطوات لا يمكن عمليا الوصول إليه وهي المسائل التي تنتمي لمجموعة NP

2- تستخدم ماكينة تورينغ لتحديد فيما إذا كانت المسألة الرياضية هي من مجموعة P أو NP

3- ماكينة تورينغ لا تحل لنا المسألة الرياضية ولكنها تخبرنا فيما إذا كان حلها سيكون محدودا P أو غير محدود NP

وأساس المعضله الأولى P V NP هي :
هل يمكن لشخص أن يثبت أمكانية أو استحالة أن تحل المسائل من نوع NP كما تحل المسائل من نوع P ؟
أي هل يمكن إثبات إمكانية أو استحالة أن تحل المسائل غير المحدودة بطرق محدودة

هل فهمي صحيح ؟
إذا كان صحيح فلدي بعض الأسئلة :

الأول
كيف يمكن لماكينة تورينج أو أي نموذج مماثل أن يعرف "عدد" الخطوات التي يمكن أن تحل أي مسألة رياضية على الرغم من أن حلها نفسه غير معروف ؟
وهذا السؤال متعلق بماكينة تورينج

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

الثالث
أساس المعضلة هو إثبات إمكانية أو استحالة تساوي P مع NP

فهل لو أتى الشخص الذي أثبت أن NP لا يمكن أن تساوي P فهل يعني ذلك إننا سنعرف أن هناك نوعية من المسائل الرياضية لا يمكن حلها عمليا ؟
وإذا أثبت هذا الشخص أن NP تساوي P فهل من المفترض أن يتضمن الحل توضيح كيفية تحويل المسائل من نوعية NP إلى P ؟ أم عليه فقط إثبات الإمكانية ويظل كيفية التحويل مطلوبة من الرياضيين الآخرين ؟

أرجو أن تعذرني إن بدت بعض الأسئلة غبية بالنسبة لك وسبب ذلك هو عدم إلمامي للموضوع

وفي النهاية أتمنى بعد الإجابة أن تنتقل للحديث عن المسائل الستة الأخرى

ملاحظة : الحل الذي قام به الشاب الروسي جورجي بيرلمان متعلق بالمعضلة الثالثة المسماه فرضية بوناكريه وهي قيد المراجعة الآن

في الختام بانتظار اجاباتك بشغف وتقبل مني كل الشكر وهذة :fs:

:bye:
صورة العضو الشخصية
المعتزلي الهاشمي
مشترك ذهبي
 
مشاركات: 128
اشترك في: الأحد يناير 22, 2006 12:56 am
الجنس: غير محدد

رقم المشاركة:#4  مشاركةبواسطة nazirkayali » الأربعاء ديسمبر 13, 2006 10:19 pm

تحية وبعد

أخ مسلم:
هل يمكن أن يكون للقرآن شفرة كالتي تحدثت عنها
و هل الحروف المقطعة و غيرها بالقرآن تشكل رسائل من الله أراد أن يفك تشفيرها جيلنا أو الأجيال التي بعدنا

سلام
صورة العضو الشخصية
nazirkayali
مشترك بلاتيني
 
مشاركات: 269
اشترك في: السبت نوفمبر 13, 2004 5:47 am
الجنس: غير محدد

رقم المشاركة:#5  مشاركةبواسطة _muslim_ » الأربعاء ديسمبر 13, 2006 11:03 pm

المسائل الرياضية على نوعين فإما إنها قابلة للحل من حيث المبدأ بعدد محدود من الخطوات وهي التي تنتمي لمجموعة P
أو غير قابلة للحل إلا بعدد هائل من الخطوات لا يمكن عمليا الوصول إليه وهي المسائل التي تنتمي لمجموعة NP

نعم هذا سليم، مع التأكيد على أن المجموعة NP لم نتمكن بعد من حسم أمرها ..
هناك عائلات أخرى من المسائل استطعنا أن نجزم بأنه "لا يمكن حلها بعدد محدود من العمليات"، أما NP فلم يحسم أمرها بعد ..

العائلة التي تضم هذا كله تسمى EXPTIME .. و هي تضم، إلى جانب P و NP مسائل أخرى كثيرة .. ثمة حوالي 400 عائلة من المسائل الرياضية ..

بعض المسائل يمكن حلها بتعقيد أبسط من P مثل المسائل L ..
و البعض يحتاج لتعقيد أكبر من NP مثل المسائل EXPTIME2 ..
و البعض لا يمكن حله أساسا (بغض النظر عن التعقيد الزمني) ..

لكن تبقى مجموعتي المسائل P و NP هما الأهم في الحياة العملية .. لأن تطبيقاتهما لا تنتهي، من نظم تشغيل الحاسب الآلي، إلى الحسابات الكونية المعقدة ..
تستخدم ماكينة تورينغ لتحديد فيما إذا كانت المسألة الرياضية هي من مجموعة P أو NP

نعم، و يمكن استخدامها لإثبات أشياء أخرى كثيرة ..
ماكينة تورينغ لا تحل لنا المسألة الرياضية ولكنها تخبرنا فيما إذا كان حلها سيكون محدودا P أو غير محدود NP

نظريا هي تقوم بحل "أي مسألة رياضية قابلة للحل" .. لكننا في الواقع لا نستخدمها إلا لتحليل المسائل، و إثبات العلاقات بينها ..
وأساس المعضله الأولى P V NP هي :
هل يمكن لشخص أن يثبت أمكانية أو استحالة أن تحل المسائل من نوع NP كما تحل المسائل من نوع P ؟
أي هل يمكن إثبات إمكانية أو استحالة أن تحل المسائل غير المحدودة بطرق محدودة

نعم .. هذا صحيح ..
كيف يمكن لماكينة تورينج أو أي نموذج مماثل أن يعرف "عدد" الخطوات التي يمكن أن تحل أي مسألة رياضية على الرغم من أن حلها نفسه غير معروف ؟

هناك طرق متعددة للإثبات ..

مثلا، أن تثبت أن حجم الخرج لمسألة معينة يكون دائما دالة أسية في حجم الدخل، و بالتالي فإن عدد العمليات الذي تحتاجه ماكينة تورنغ لإنتاج هذا الخرج لابد و أن يكون دالة أسية في حجم الدخل (على الأقل) ..

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

لماذا؟ لأن المسألة (ب) لو كانت ذات تعقيد زمني متعدد الحدود، فإن هذا يعني أننا قد عثرنا على طريقة لحل (أ) بتعقيد زمني متعدد الحدود، و ذلك عن طريق تحويل (أ) إلى (ب)، ثم حلها .. و هذا ما يتناقض مع الحقائق المثبتة من قبل، من أن المسألة (أ) لها تعقيد زمني أسي ..
هذا ما يسمى الإثبات بالتناقض Proof By Contradiction

يمكنك أيضا أن تثبت أن المسألة يمكن حلها بتعقيد زمني متعدد الحدود، بأن تجد لها حلا متعدد الحدود .. و هو ما يعرف بالإثبات البناء Constructive Proof .. لاحظ أننا هنا نحتاج لمعرفة حل للمسألة ..

معرفتك لطريقة حل المعضلة الرياضية لا يفيدك إلا بشكل جزئي، فلنفرض أنك تمتلك طريقة لحل مسألة معينة، و يمكنك بالتالي قياس حجم العمليات المطلوب القيام به للوصول إلى الحل .. فكيف تضمن أنه لا توجد طريقة أخرى لحل مسألتك بعدد أقل من العمليات؟! (لا حظ أن هذه هي مشكلتنا مع الـNP لأننا لا نستطيع أن نجزم بأننا قد وصلنا إلى أكثر الحلول بساطة بعد)

هناك أساليب متعددة للإثبات في الرياضيات .. بعضها يستند لأساليب معقدة من المنطق الرياضي Mathematical Logic ..
هل يمكن أن تعطينا أمثلة عن نوعية المسائل من نوع P والمسائل من نوع NP ؟

من أمثلة النوع P .. الحساب العادي (الجمع و الضرب) Arithmetics.. ترتيب مجموعة من الأرقام تصاعديا أو تنازليا Sorting .. تحديد أكبر قاسم مشترك بين رقمين Greatest Common Divisor

مسائل النوع NP متقدمة نوعا ما، و يطول شرحها، مثل كسر الشفرات Crytanalysis و تحديد القيم التي تجعل صيغة منطقية معينة صحيحة Satifiability problem ..
لكني ذكرت لك مثالا مبسطا على مسائل الـNP، و هو ما يسمى بـ"معضلة البائع الجائل" .. و تتعلق بحساب أقصر مسار يمر بمجموعة من المدن، بحيث يغطي جميع المدن، دون المرور على مدينة واحدة مرتين ..
أعتقد أنه يفي بالغرض ..
وهل المسائل المتعلقة بالآنظمة المعقدة - الفوضى- مثل الأحوال الجوية تعتبر من ضمن مسائل NP ؟ أم هو أمر آخر ؟

التعقيد الذي تتكلم عنه هو تعقيد النظم، و هو يختلف عن التعقيد الحسابي .. لكن هذا لا يمنع أن المسائل المتعلقة بالنظم المعقدة، يمكن إخضاعها للتحليل الرياضي، كأي مسائل أخرى، بحيث نعرف تعقيدها الحسابي ..
فهل لو أتى الشخص الذي أثبت أن NP لا يمكن أن تساوي P فهل يعني ذلك إننا سنعرف أن هناك نوعية من المسائل الرياضية لا يمكن حلها عمليا ؟

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

لو أثبت الشخص أن المجموعتين متساويتين، إثباتا رياضيا صحيحا، لكفاه ذلك .. لكن في الغالب يكون من الصعب إثبات ذلك بدون توضيح كيفية تحويل المسائل NP إلى P ..
أرجو أن تعذرني إن بدت بعض الأسئلة غبية بالنسبة لك وسبب ذلك هو عدم إلمامي للموضوع

بالعكس يا أخي، أسئلتك في موضعها ..
وفي النهاية أتمنى بعد الإجابة أن تنتقل للحديث عن المسائل الستة الأخرى

كنت أود ذلك أخي .. لكن مجال دراستي هو الحوسبة النظرية، و ليس الرياضة البحتة، و لذلك لم أتطرق إلا للمسألة الأولى ..

أترك المجال الآن لمن له دراية ببقية المواضيع .. و أتمنى لك حظا وافرا
صورة العضو الشخصية
_muslim_
مشترك فضِّي
 
مشاركات: 97
اشترك في: الأحد مارس 12, 2006 4:04 am
مكان: Canada
الجنس: غير محدد

رقم المشاركة:#6  مشاركةبواسطة المعتزلي الهاشمي » الخميس ديسمبر 21, 2006 4:24 pm

أخ مسلم

لك كل الشكر على هذا التوضيح والشرح
من باب الفضول أرجو أن تعطيني فكرة عن نوعية المسائل التي تم الجزم باستحالة حلها بعدد محدود من العمليات

بانتظار شرح عن المسائل الأخرى

تحياتي
:bye:
صورة العضو الشخصية
المعتزلي الهاشمي
مشترك ذهبي
 
مشاركات: 128
اشترك في: الأحد يناير 22, 2006 12:56 am
الجنس: غير محدد

رقم المشاركة:#7  مشاركةبواسطة _muslim_ » الخميس ديسمبر 21, 2006 9:56 pm

من أشهر المسائل التي أثبت العلماء عدم إمكانية حلها بتعقيد زمني متعدد الحدود، هي بعض مما يندرج تحت بند نظرية الألعاب Game Theory .. مثل الشطرنج.

يمكن أن نمثل رقعة الشطرنج في لحظة معينة كمسألة رياضية .. حيث أن الوضع الحالي للقطع هو معطيات المسألة، و الخطوة التي يتعين علينا اتخاذها هي حل المسألة ..
يعتبر الحل صحيحا إذا كان سينتهي بنصر اللاعب، و فيما عدا ذلك يكون الحل خاطئا .. و تقدم لنا نظرية الألعاب Game Theory من أدوات رياضية، ما يمكننا استخدامه لحل المسألة، و اتخاذ القرار المناسب .. لكن ذلك لا يمكن أن يتم أبدا بتعقيد زمني متعدد الحدود.

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


نعود إلى موضوعنا .. هناك أيضا مسائل لا يمكن حلها أبدا، بغض النظر عن التعقيد الزمني (أي أنها لا تُحل، لا بتعقيد زمني محدود، و لا غير محدود) .. تسمى هذه المسائل مسائل غير قابلة للحسم undecidable ..

من الأمثلة على ذلك، عند تحليل أحد برامج الكمبيوتر، لا يمكننا أبدا (مهما استخدمنا من أدوات رياضية) أن نحسم إن كان هذا البرنامج سيتوقف بعد وقت محدود أم أنه سيدخل في دورة لانهائية Infinite Loop ..
إن إيجاد طريقة رياضية يمكنها حسم هذا السؤال، لجميع برامج الكمبيوتر، هو أمر مستحيل.

كذلك، من المسائل الغير قابلة للحسم، مسألة قياس التعقيد الزمني للمسائل ..
أي أنه من المستحيل أن توجد طريقة رياضية معينة، يمكنها معرفة التعقيد الزمني لجميع المسائل الرياضية الأخرى.
صورة العضو الشخصية
_muslim_
مشترك فضِّي
 
مشاركات: 97
اشترك في: الأحد مارس 12, 2006 4:04 am
مكان: Canada
الجنس: غير محدد

رقم المشاركة:#8  مشاركةبواسطة المعتزلي الهاشمي » الجمعة ديسمبر 22, 2006 11:12 am

مسلم

شكرا لك أخي الكريم على منحي هذا الشرح والوقت

تحياتي :fs:
صورة العضو الشخصية
المعتزلي الهاشمي
مشترك ذهبي
 
مشاركات: 128
اشترك في: الأحد يناير 22, 2006 12:56 am
الجنس: غير محدد

Re: أهم 7 مسائل رياضية غير محلولة في هذا العصر

رقم المشاركة:#9  مشاركةبواسطة Taylur » الجمعة أغسطس 29, 2008 1:35 am

muslim

لقد عالجت الرياضيات في قسم نظرية البيان Graph Theory مثل هذه المسائل ومن النماذج المدروسة هي Hamilton Cycle عن طريق إيجاد خوارزميات حاسوبية من شأنها حل مثل هذه المسائل اللامنطقية أحياناً...
ولكن السؤال هل الرياضيات قادرة على حل كل شيء؟
الجواب نعم بل وأكثر من ذلك هي العلم الذي سبق الحاضر وتجاوزه إلى المستقبل ...


مع محبتي
كل قلوب الناس جنسيتي، فلتسقطوا عني جواز السفر


ياإلهي أنه النجم يطلع ... دعه يغني لنا إننا التعساء ... عذبتنا ما استطعت
صورة العضو الشخصية
Taylur
مشترك ذهبي
 
مشاركات: 230
اشترك في: الثلاثاء يوليو 01, 2008 3:13 pm
مكان: مجرة درب التبانة - الذراع السادس
الجنس: ذكر


العودة إلى الساحة العلميّة

الموجودون الآن

المستخدمون المتصفحون لهذا المنتدى: لا يوجد أعضاء مسجلين متصلين و 4 زائر/زوار

Site Login