لغة موجزة

الموسوعة الحرة

في نظرية التعقيد الحسابي ، تُعرَّف اللغة المتفرقة بأنها لغة رسمية (مجموعة من السلاسل النصية ) بحيث تكون دالة التعقيد ، التي تحسب عدد السلاسل النصية ذات الطول n في اللغة، محدودة بدالة متعددة الحدود لـ n . تُستخدم هذه اللغات بشكل أساسي في دراسة العلاقة بين فئة التعقيد NP والفئات الأخرى. تُسمى فئة تعقيد جميع اللغات المتفرقة SPARSE .

جميع اللغات الأحادية هي لغات متفرقة، وهذا أمر بديهي. ونتيجة لذلك، يُستخدم مفهوم اللغة المتفرقة عادةً فقط للغات التي تحتوي على حرفين على الأقل.

تُسمى اللغات المتفرقة متفرقة لأنها تعتمد على أبجدية محدودة.Σ{\displaystyle \Sigma }هناك|Σ|ن{\displaystyle {|\Sigma |}^{n}}سلاسل بطول n . لذا، عندما لا تكون اللغة أحادية، فإن احتمال انتماء سلسلة عشوائية منتظمة بطول n إلى اللغة يتقارب أُسّيًا إلى 0

أمثلة

لأي عدد صحيح ثابت k ، لنعتبر مجموعة السلاسل الثنائية التي تحتوي بالضبط على k تكرارًا للبت1{\displaystyle 1}لكل قيمة n ، يوجد فقط(نك)≲نك{\displaystyle {\binom {n}{k}}\lesssim n^{k}}السلاسل النصية في اللغة. لذا فهي متفرقة.

العلاقات مع فئات التعقيد الأخرى

  • تحتوي SPARSE على TALLY ، وهي فئة اللغات الأحادية ، حيث أن هذه اللغات تحتوي على سلسلة واحدة على الأكثر من أي طول واحد.
  • E ≠ NE إذا وفقط إذا كانت هناك لغات متفرقة في NP ليست في P. [ 1 ]
  • إذا كانت أي لغة متفرقة صعبة الحل من نوع NP فيما يتعلق باختزالات تورينج ، فإن PH تنهار إلىΔ2P{\displaystyle \Delta _{2}^{P}}هذا نتيجة لنظرية كارب-ليبتون . [ 2 ] وقد تم تحسين هذه النتيجة في عام 2005، مما أظهر أن انهيار PH يكون أعمق منΔ2P{\displaystyle \Delta _{2}^{P}}[ 3 ]​

نظرية ماهاني

أظهر (فورتشن، 1979) أنه إذا كانت أي لغة متفرقة كاملة من نوع NP ، فإن P = NP . [ 4 ] استخدم (ماهاني، 1982) هذا لإثبات نظرية ماهاني التي تنص على أنه إذا كانت أي لغة متفرقة كاملة من نوع NP ، فإن P = NP . [ 5 ] لا تتطلب حجة ماهاني بالضرورة أن تكون اللغة المتفرقة ضمن فئة NP (لأن وجود مجموعة متفرقة صعبة من نوع NP يستلزم وجود مجموعة متفرقة كاملة من نوع NP)، لذا توجد مجموعة متفرقة صعبة من نوع NP إذا وفقط إذا كانت P = NP . [ 6 ]

(أوجيهارا وواتانابي، 1991) يقدم برهانًا مبسطًا لنظرية ماهاني استنادًا إلى المجموعات اليسرى. [ 7 ]

أظهر (جين-يي كاي ودي . سيفاكومار، 1999)، استنادًا إلى عمل أوجيهارا، أنه إذا كانت هناك لغة متفرقة كاملة من النوع P تحت اختزال logspace (متعدد-واحد) ، فإن L = P. [ 8 ]

بولي

على الرغم من أن ليس كل اللغات في P /poly متفرقة، إلا أن هناك اختزالًا تورينجيًا في وقت متعدد الحدود من أي لغة في P /poly إلى لغة متفرقة. [ 9 ]

يوجد اختزال تورينج (على عكس اختزال كارب من نظرية ماهاني) من لغة كاملة من فئة NP إلى لغة متفرقة إذا وفقط إذاNP⊆P/بولي{\displaystyle {\textbf {NP}}\subseteq {\textbf {P}}/{\text{poly}}}.

مراجع

  1. ↑ جوريس هارتمانيس، نيل إيمرمان، فيفيان سيولسون. المجموعات المتفرقة في NP-P: EXPTIME مقابل NEXPTIME. المعلومات والتحكم ، المجلد 65، العدد 2/3، الصفحات 158-181. 1985. في مكتبة ACM الرقمية
  2. ↑ كارب، ريتشارد م .؛ ليبتون، ريتشارد ج. (1980). "بعض الروابط بين فئات التعقيد غير المنتظم والمنتظم". في: ميلر، ريموند إي.؛ جينسبيرغ، سيمور؛ بوركهارد، والتر أ.؛ ليبتون، ريتشارد ج. (محررون). وقائع الندوة السنوية الثانية عشرة لجمعية آلات الحوسبة حول نظرية الحوسبة، 28-30 أبريل 1980، لوس أنجلوس، كاليفورنيا، الولايات المتحدة الأمريكية . جمعية آلات الحوسبة. الصفحات 302-309 . doi : 10.1145/800141.804678 . 
  3. ^ كاي، جين يي؛ تشاكارافارثي، فينكاتيسان تي؛ هيماسباندرا، لين أ؛ أوجيهارا، ميتسونوري (2003). البديل، هيلموت. حبيب، ميشيل (محرران). "يؤدي المتنافسون المتنافسون إلى تحسين نتائج انهيار كارب-ليبتون" . ستاكس 2003 . برلين، هايدلبرغ: سبرينغر: 535-546 . دوى : 10.1007 / 3-540-36494-3_47 . رقم ISBN 978-3-540-36494-8.
  4. ↑ إس. فورتشن. ملاحظة حول المجموعات الكاملة المتفرقة. مجلة SIAM للحوسبة ، المجلد 8، العدد 3، الصفحات 431-433. 1979.
  5. ↑ إس آر ماهاني. المجموعات الكاملة المتفرقة لـ NP: حل تخمين بيرمان وهارتمانيس. مجلة علوم الحاسوب والنظم 25: 130-143. 1982.
  6. ^ بالكازار، خوسيه لويس. دياز، جوزيب؛ جابارو، يواكيم (1990). التعقيد الهيكلي الثاني . سبرينغر . ص 130 – 131. ISBN  3-540-52079-1.
  7. ↑ أوجيوارا، ميتسونوري؛ واتانابي، أوسامو (1991). "حول إمكانية اختزال جداول الحقيقة المحدودة زمنيًا لمجموعات NP إلى مجموعات متفرقة". مجلة SIAM للحوسبة . 20 (3): 471-483 . doi : 10.1137/0220030 . MR 1094526 . 
  8. ↑ كاي، جين-يي؛ سيفاكومار، د. (1999-04-01). "المجموعات الصلبة المتفرقة لـ P" . مجلة علوم الحاسوب والأنظمة . 58 (2): 280-296 . doi : 10.1006/jcss.1998.1615 . ISSN 0022-0000 . 
  9. ↑ جين-يي كاي. المحاضرة 11: P=poly، المجموعات المتفرقة، ونظرية ماهاني. CS 810: مقدمة في نظرية التعقيد. جامعة ويسكونسن-ماديسون. 18 سبتمبر 2003 (PDF)