КӨПМҮШЕЛIК САҚИНАСЫНЫҢ ПУНКТУАЛДЫ ЖӘНЕ КӨПМҮШЕЛIК УАҚЫТТА ЕСЕПТЕЛЕТIН ПРЕЗЕНТАЦИЯЛАРЫ ТУРАЛЫ

Аңдатпа

Бұл жұмыста сақиналы көпмүшелiктердiң пунктуалды және көпмүшелiк уақытта есептелетiн презентацияларының бар болуы мен қасиеттерi зерттеледi. Бiз бiр айнымалысы бар R[x] көпмүшелiк сақинасына назар аударамыз, мұндағы R — бiрлiгi бар коммутативтi сақина, және осы құрылымның примитивтi рекурсивтi (п.р.) және пунктуалды презентациясының бар болуы үшiн салыстырмалы түрде қарапайым критерий белгiлеймiз. Пунктуалды есептелу ұғымы, яғни құрылымның атомдық диаграммасы нақты уақытта есептелуi талап етiледi, соңғы кездерi есептелетiн модельдер теориясында өзiнiң табиғи алгоритмдiк түсiндiрмесiне байланысты айтарлықтай назар аудартты. Бiз R[x] сақинасының п.р. және пунктуалды презентациясы R базалық сақинасына қойылатын жұмсақ алгебралық болжамдар кезiнде бар болатынын дәлелдеймiз, осылайша есептелетiн сақиналар туралы бұрынғы белгiлi нәтижелердi жалпылаймыз. Сонымен қатар, бiз R[x]-тiң көпмүшелiк уақытта есептелетiн (P-есептелетiн) презентациясын зерттеймiз және мұндай презентация базалық R сақинасы P-есептелетiн презентацияға ие болған кезде табиғи түрде пайда болатынын көрсетемiз. Атап айтқанда, көпмүшелiк сақиналардың стандартты құрылымы көпмүшелiк есептелудi сақтайтынын және сақиналық амалдардың тиiмдi көрсетiлiмiн беретiнiн дәлелдеймiз. Сонымен қатар, бiз R[x]-тiң пунктуалды өлшемдiлiгiн талдаймыз және дихотомияны белгiлеймiз: пунктуалды өлшемдiлiк не дәл 1-ге тең, не шексiздiкке тең, аралық мәндер мүмкiн емес. Бұл классификация өткiр құрылымдық шекараны айқындайды және тиiмдi алгебра мен есептеу күрделiлiгi теориясы арасындағы байланысқа жаңа көзқарастар ұсынады.