المتتاليات مع قيود الفجوات العامة: حدود التعقيد العليا والسفلى

بالنسبة لسلسلتين u و v من بعض الأبجدية A، نحقق في مشكلة تضمين u في w كمتتاليات في وجود قيود الفجوات العامة. constraint هي ثلاثة (i ، j ، C₈ ، ₉)، حيث 1 <= i < j <= |u| و C₈ ، ₉ هو مجموعة فرعية من A^*. يعني تضمين u كمتتالية في v بحيث يتم تلبية (i ، j ، C₈ ، ₉) أنه إذا كانت ui و uj مرتبطة بـ vk و vl على التوالي، فإن الفجوة المستحثة vk + 1. . l - 1 يجب أن تكون سلسلة من C₈ ، ₉. هذا يعمم الإعداد الذي تم التحقيق فيه حديثًا في Day وآخرون، ISAAC 2022، حيث تمت معالجة قيود الفجوات فقط من الشكل C₈ ، ₈ + ₁، بالإضافة إلى الإعداد من Kosche وآخرون، RP 2022، حيث تمت معالجة قيود الفجوات فقط من الشكل C₁، |ₔ|. نوضح أن تطابق المتتاليات تحت قيود الفجوات العامة هو NP-hard، ونكمل هذا الحد الأدنى العام بتحليل تعقيد شامل (مُعاد تخصيصه). علاوة على ذلك، نحدد عدة فئات فرعية قابلة للحل بكفاءة تنتج عن تقييد هيكل الفاصل الناتج عن قيود الفجوات العامة.