مشكلة سكوليم

📅 آخر تحديث: ٢٥ يوليو ٢٠٢٦
✍️ نُشر في: ٢٥ يوليو ٢٠٢٦
الموسوعة الحرة
مشكلة لم تُحل في الرياضيات
هل توجد خوارزمية لاختبار ما إذا كان للمتتالية الثابتة المتكررة صفر؟
المزيد من المسائل غير المحلولة في الرياضيات

في الرياضيات ، تُعرف مسألة سكوليم (وتُسمى أيضًا مسألة سكوليم-بيزو [ 1 ] ) بأنها مسألة تحديد ما إذا كانت قيم متتالية ثابتة متكررة تتضمن العدد صفر. يمكن صياغة هذه المسألة لتكرارات على أنواع مختلفة من الأعداد، بما في ذلك الأعداد الصحيحة والأعداد النسبية والأعداد الجبرية . ولا يُعرف ما إذا كانت هناك خوارزمية قادرة على حل هذه المسألة. [ 2 ]

تُعبّر علاقة التكرار الخطي عن قيم متتالية من الأرقام كتركيبة خطية من القيم السابقة؛ على سبيل المثال، يمكن تعريف أعداد فيبوناتشي من علاقة التكرار

F ( n ) = F ( n  − 1) + F ( n  −  2)

بالإضافة إلى القيمتين الابتدائيتين F (0) = 0 و F (1) = 1. سُميت مسألة سكوليم نسبةً إلى ثورالف سكوليم ، نسبةً إلى بحثه المنشور عام 1933 الذي أثبت فيه نظرية سكوليم -مالر-ليخ حول أصفار متتالية تحقق علاقة تكرارية خطية بمعاملات ثابتة . [ 3 ] تنص هذه النظرية على أنه إذا كانت لهذه المتتالية أصفار، فإن مواقع الأصفار تتكرر بانتظام، باستثناء عدد محدود من الحالات. أثبت سكوليم هذه النظرية للعلاقات التكرارية على الأعداد النسبية، ثم وسّعها ماهلر وليخ لتشمل أنظمة أعداد أخرى . مع ذلك، لا توضح براهين النظرية كيفية اختبار وجود أي أصفار.

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

توجد حلول جزئية لمسألة سكوليم، تغطي الحالة الخاصة للمسألة المتعلقة بالتكرارات من الدرجة الرابعة على الأكثر. ومع ذلك، لا تنطبق هذه الحلول على التكرارات من الدرجة الخامسة أو أعلى. [ 2 ] [ 5 ] [ 6 ]

بالنسبة للعلاقات التكرارية الصحيحة، من المعروف أن مشكلة سكوليم هي مشكلة صعبة من نوع NP . [ 7 ]

انظر أيضاً

مراجع

  1. ↑ لوكا، فلوريان؛ أواكنين، جويل؛ ووريل، جيمس (2022). سزيدر، ستيفان؛ غانيان، روبرت؛ سيلفا، ألكسندرا (محررون). مجموعة سكوليم عالمية ذات كثافة دنيا موجبة . المجلد  241. الصفحات  73:1–73:12. doi : 10.4230/LIPIcs.MFCS.2022.73 . ISBN 978-3-95977-256-3.
  2. 1 2 3 أواكنين، جويل؛ ووريل، جيمس (2012)، "مسائل القرار لمتتاليات التكرار الخطي"، مسائل الوصول: ورشة العمل الدولية السادسة، RP 2012، بوردو، فرنسا، 17-19 سبتمبر 2012، وقائع ، سلسلة محاضرات في علوم الحاسوب، المجلد 7550، هايدلبرغ: سبرينغر-فيرلاغ، الصفحات 21-28 ، doi : 10.1007/978-3-642-33512-9_3 ، ISBN   978-3-642-33511-2MR 3040104​ .
  3. ^ سكوليم، ث. (1933)، "Einige Sätze über gewisse Reihenentwicklungen und exponentiale Beziehungen mit Anwendung auf diophantische Gleichungen"، أوسلو فيد. أكاد. سكريفتر ، أنا (6). بدلاً من ذلك، يستشهد Ouaknine & Worrell (2012) بورقة بحثية لسكوليم تعود إلى عام 1934 للحصول على هذه النتيجة.
  4. ^ بيرستل، جان؛ مينوت ، موريس (1976)، “Deux propriétés décidables des suites récurrentes linéaires” ، Bulletin de la Société Mathématique de France (بالفرنسية)، 104 (2): 175– 184، دوى : 10.24033/bsmf.1823 ، MR 0414475 .
  5. ^ مينوت، م. الأماكن القريبة : Tijdeman، R. (1984)، “المسافة بين مصطلحات تسلسل التكرار الجبري”، Journal für die Reine und Angewandte Mathematik ، 349 : 63–76 ، MR 0743965 .
  6. ↑ فيريشاجين، ن.ك. (1985)، "مشكلة ظهور الصفر في متتالية خطية متكررة"، مجلة الرياضيات (بالروسية)، 38 (2): 177-189 ، 347، MR 0808885 .
  7. ↑ بلونديل، فنسنت د.؛ بورتييه، ناتاشا (2002)، "تحديد وجود صفر في متتالية خطية متكررة عددية هو مسألة صعبة الحل من نوع NP"، الجبر الخطي وتطبيقاته ، 351/352: 91-98 ، doi : 10.1016/S0024-3795(01)00466-9 ، MR 1917474 .