Қиындықтар әр түрлі болуы мүмкін. түрлі есептеуіш модельдер?

Мен шешімнің шешімі белгілі бір есептік модельдерге қатысты шешуші болуы мүмкін екенін түсінемін. Мысалы, жақшаның еркін дәйектілігі теңдестірілген болып табыла ма, мәселе соңғы автоматтандырылған автоматтандыру үшін жарамсыз және автоматтандыру автоматтары үшін жарамсыз.

Мәселелердің күрделілігіне байланысты ұқсас нәрсе бар ма? Мысалы, бір есептеуіш моделіне қатысты $ \ mathbf {P} $ болатын проблемалар бар ма, бірақ $ \ mathbf {EXPTIME} \ setminus \ mathbf {P} $ қатаң нашар қатысты?

3
@babou, мен төмен дауыс бердім және тақырыпты жабу үшін дауыс алдым: Niel айтқан сияқты негізгі түсінбеушілік бар, және егер олар бекітілсе, мәселе әлдеқайда әлсіз модельдер сияқты анық емес. Егер одан кейін біз одан тыс П-дан тыс ақылға қонымды/шынайы модельдерде есептелетін политимге назарымызды шектей алсақ, онда менің жауапым Күрделі-Теориялық Шіркеу-Туринг Диссертациясы үшін Google болады.
қосылды автор Swinders, көзі
Мен ешқандай қиындықсыз сарапшы емеспін. Бірақ менің ойымша, бұл мәселе мағынасы бар, бірақ оның мәлімдемесі дұрыс терминологияны пайдаланбауы мүмкін. Неге төмендету? Себебі, сіз оны TCS үшін орынсыз деп есептесеңіз: айталық, кем дегенде. Немесе оны CS-ге жіберу үшін белгілеңіз.
қосылды автор Martin Vobr, көзі
@SureshVenkat Мен бір уақытта сіз түсіндірдім. Маған оның есептік моделіне қатысты жарамсыздық туралы сөйлесудің алға басқан жолы ұнады (бұл қабылданған көзқарас, әлде жасырын тұзақ бар ма?). Сіз қалай ойлайсыз, сұрақты жақсы түрде қайта бөле аласыз ба? Менде мәселенің нәзіктігін түсіну үшін тәжірибем жоқ, және менің ойымша, Niel de Beaudrap түсіндірмесінің түсініктемесі жоқ.
қосылды автор Martin Vobr, көзі
@NieldeBeaudrap рахмет. Мен оған нәзік нәрсе бар деп ойладым. Маңызды мәлімдеме (мүмкін, сарапшыларға әрдайым түсініксіз), бұл күрделілік класы - бұл мәселелердің жиынтығы , әдетте оларды сипаттайтын есептеу үлгісі мен ресурстары мен сипаттамалары бойынша сипатталады немесе дәлелденеді басқа баламалы комбинациялар болуы мүмкін). Ол (un) decidable -мен ұқсастығын ескере отырып, ОС-ның қателігі негізінен « уақыт полиномиальды » орнына P , ешкім түсіндірмеді. Неліктен?
қосылды автор Martin Vobr, көзі
Дегенмен, менің ойымша, төменде жатқан пайдалы мәселе бар.
қосылды автор alumb, көзі
Әдетте өздерін сұрамайынша, біз ОС мәселесін қайта топтастырмаймыз.
қосылды автор alumb, көзі
Күрделілік сыныптарымен («

P ?» Осы проблема бар) жұмыс уақытын шатастырмау керек («бұл есептеу моделі осы мәселені полиномиальді уақытта шеше алады?»). Сыныптау машинасындағы (және есептеудің көп уақыттық балама модельдері) полиномиальді уақытта шешілетін мәселелерге P класы жатады. Басқа кластар басқа модельде полиномиальді уақытты есептеуді білдіреді: BPP және BQP - мысалы, (шектеулі қателігі) .

қосылды автор Niel de Beaudrap, көзі
@Babou: Мәселе әртүрлі күрделілік класстарын есептеудің әртүрлі үлгілерімен полиномиальді уақытта шешілетін мәселелер жиынтығы ғана емес, оның анықтамасы моделмен өзгеретіні емес. Яғни, егер әртүрлі есептеу модельдеріндегі полиномиальдық уақыт алгоритмдері туралы сөйлескісі келсе, оны жай ғана айту керек және оны P -парансқа түсіруге тырыспаңыз .
қосылды автор Niel de Beaudrap, көзі
@NieldeBeaudrap: жақсы нүкте! Егер күрделілік класстарының анықтамасын іздеп жүрген болсам, онда мен өзім үшін ойлаған едім. Терминологиядағы пікірталастан аулақ болу үшін менің мысалдарымды мұқият таңдаған болар еді :)
қосылды автор RustyStatistician, көзі

2 жауаптар

Niel De Beaudrap нүктесі маңызды: күрделілік класы машина үлгісі бойынша деп анықталады. Бірақ егер сіз өзіңіздің мәселеңізді қайта түсіндіретін болсаңыз:

Мәселе күрделілігі әртүрлі есептеуіш модельдерде айтарлықтай ерекшелене ме?

Сонда жауап - иә. JeffE-ның жауабына менің алдыңғы сұрағым шешімді шешу қиындықтары туралы күрделі мәселе многодинамической шешім ағашының күрделілігі бар NP-қиын мәселенің мысалы (SUBSET SUM).

7
қосылды
Басқа сөз қажет (басқа күрделілік ). Мен Niel de Beaudrap керісінше сөйлеп тұрғанын түсіндім. Күрделілігі мен күрделілігі сыныптары есептік модельдерден тәуелсіз. Мүмкін, мұнда уақытты, кеңістікті немесе қажет болғанда өлшеуге арналған шығындар сөзін қолданған жөн бе, бұл есептеу үлгісіне байланысты. Сұраққа жауап беруімнің үстінен қараңыз
қосылды автор Martin Vobr, көзі
Менің қателігім танымал күрделі сыныптар үшін анықтаманы қабылдау еді, ал мен оны оңай көре алатын едім. Мен Niel de Beaudrap түсініктемелерін бақылау ретінде қабылдаймын, сонымен қатар classes күрделілігі дәл есептеу әдісімен анықталады. Дегенмен, күрделілік әлі де дұрыс термин.
қосылды автор RustyStatistician, көзі

Another well known example of how a Turing complete computational model can lead to a time complexity blow-up is 2 Counter Automata (2CA)

2CA екі тіркеліммен жабдықталған, ол шексіз неотрицательный бүтін сандарды сақтай алады және тек қарапайым нұсқауларды азайту/санауыштарды, шартты секірулерді (есептегіш нөлге тең немесе жоқ па) тексеріп, сөзсіз секіруді орындауға қабілетті. Кіріс екі санауыштың біріне орналастырылады, сондықтан оны unary ішінде көрсету керек.

A 2CA еркін $ 1 $ $ x $ кірісіне Turing машинасын $ M $ имитациялауға болады, бірақ оның кірісі $ 2 ^ x $ деп орнатылған болса ғана. Осылайша, $ M $ $ x $ -ға әрбір симуляциялық таспа операциясы экспоненталық уақытты талап етеді.

3
қосылды