ما هي أنواع خصائص السلسلة التي يمكن التحقق منها في وقت متعدد الحدود؟

Question

عند إعطاء السلسلة والخاصية المعنية كشهادة محتملة. هل هناك أي نظرية تصنيف يقول شيئا على غرار: جميع الخصائص (السلاسل) التي تحتوي على هذه الخاصية (كخاصية فرعية) يمكن التحقق منها في وقت متعدد الأصناف؟

هل هناك أي مجموعات من أنواع الأنماط في السلاسل التي يمكن التحقق منها في بولي وقت؟

خاصية تافهة هي أن مجموعة من السلاسل مع هذه الخصائص تنتمي إلى لغة في NP (تنتمي إلى NP كونها الخاصية الفرعية).

أنا أبحث عن شيء أكثر ملموسة.

أنا أبحث عن موضوع مشترك بين خصائص السلسلة مثل هذه التي تجعل هذه الخصائص يمكن التحقق منها في بولي وقت لأي سلسلة.

ie.e. هل هناك طريقة لاختيار خصائص الأوتار من قبعة بهذه الطريقة التي تكون فيها الخصائص التي تختارها أن تكون قابلة للتحقق في وقت بولي في أي سلسلة.

ربما هناك طريقة للقيام بذلك مع تعقيد ضمني - حيث الخصائص الوحيدة التي يمكنك بناءها (في بعض اللغة المقيدة) هي تلك التي يمكن التحقق منها في بولي وقت؟

Answer 1

التحقق من خاصية السلاسل عبر الأبجدية $ \ Sigma $ هي بالضبط نفس المشكلة مثل التحقق مما إذا كانت السلسلة جزءا من لغة، تسمى Entscheidungsproblem أو القرار مشكلة.

اللغة: $ \ sigma ^ * \ mapsto \ {0،1 \} $

ما الذي تهتم به هي "خصائص السلاسل" أو بمعنى آخر من فئات اللغات ".

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

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