مبرهنة شوارتز-زيبل

Question book-new.svg
تعرَّف على طريقة التعامل مع هذه المسألة من أجل إزالة هذا القالب.يفتقر محتوى هذه المقالة إلى الاستشهاد بمصادر. فضلاً، ساهم في تطوير هذه المقالة من خلال إضافة مصادر موثوقة. أي معلومات غير موثقة يمكن التشكيك بها وإزالتها. (مارس 2016)

مبرهنة شوارتز -زيبل هي نتيجة اساسية في علم الاحتمال ولها تأثير على عدة مجالات في الرياضيات وعلم الحاسوب

مقدمةعدل

من الشائع جدا معرفة متطابقات متعددة الحدود مثل :   أو مبرهنة المربعات الأربع للاغرانج وهي :   وهناك طريقة بسيطة لفحص هذه المتطابقات وهي عن طريق فتح الأقواس وفحص كل منهما إذا ما كانا متطابقين ! ولكن هذه العملية هي عملية أُسية بالنسبة لطول المدخل، إذ ان عدد احادية الحدود الناتجة عدد هو   عندما d هو اعلى درجة احادي الحدود وما نريده إذا هي خوارزمية سريعة (اي تعقيدها الوقتي هو متعدد حدود بالنسبة للمدخل ) ولكن هذا غير معلوم للان ومبرهنة شوارتز-زيبل تعطينا خوارزمية احتمالية سريعة .

تعريف المسألةعدل

مسألة تطابق متعددات الحدود هي : معطى دائرة حسابية   والتي تحسب متعدد الحدود   في   , جد خوارزمية حتمية التي تفحص إذا ما p صفر ويستخدم فقط   حسابات في  

المبرهنةعدل

لنفرض ان   متعدد حدودي ليس صفرا ودرجته   فوق حقل   ولنفرض ان S مجموعة جزئية نهائية ل-  حينها :

 

البرهانعدل

سوف نستخدم استقراء رياضي (Induction) على n ,

إذا n=1 , حسب المبرهنة الأساسية في الجبر هناك على الأكثر d جذور لذا فان المبرهنة تصح في هذه الحالة اي انه :  

لنفرض ان المبرهنة صحيحة لكل متعددات الحدود مع   متغيرات وبدون تقييد العموم نستطيع ان نفترض ان   متعدد الحدود ب-  ونستطيع ان نكتبه بالطريقة التالية :

 

بما ان   ليس صفرا يوجد i بحيث ان   ليس صفراً ونختار i ليكون الأكبر وصفته كما هو مذكور، مفهوم ضمنا أن   وذلك لان متعدد احادي الحدود   درجته i وبما ان حاصل ضرب متعدد الحدود :  مع احادي الحدود هذا هو على الأكثر d لذا فان هذه الصفة صحيحة . الان نختار عشوائيا   من   , وحسب فرضية الاستقراء الرياضي :

 

.

إذا   حينها   والذي يحوي متغير واحد فقط ما يعيدنا للحالة الاساسية للاستقراء الرياضي اي :

 

حينها :

 

استخداماتعدل

  1. هذه المبرهنة تقول بانه إذا كان عندنا في الحقل   على الاقل   اعداد عندها يوجد خوارزمية احتمالية واحتمال خطأه على الأكثر   وفي حالة انه يوجد اقل حينها نوسع   ونختار نقاط عشوائية لذا فان هذه المسألة تتبع قسم التعقيد co-RP .
  2. المبرهنة والتي تبحث مسألة تطابق متعددي حدود لها الكثير من التطبيقات في علم الحاسوب والرياضيات حيث ان مسألة التطابق كانت مهمة في برهنة   مسألة اخرى هي فحص إذا ما مخطوط معطى هو مخطط ثنائي وذلك حسب نظرية برهنها Tutte . ويمتد استخدامها لفحص إذا ما معطى عدد هو اولي .