Ամսագրի կամ հրապարակման վերնագիր:

Математические вопросы кибернетики и вычислительной техники=Կիբեռնետիկայի և հաշվողական տեխնիկայի մաթեմատիկական հարցեր=Mathematical problems of computer science

Հրապարակման ամսաթիւ:

2024

Համար:

61

ISSN:

2579-2784 ; e-2538-2788

Լրացուցիչ տեղեկութիւն:

Мокацян Арсен А., Барсегян Хачатур А., Մոկացյան Արսեն Հ., Բարսեղյան Խաչատուր Ա.

Այլ վերնագիր:

P-m-митотические множества и арифметическая иерархия ; P-m-միթոտիկ բազմություններ և թվաբանական աստիճանակարգ

Ծածկոյթ:

50-61

Ամփոփում:

Let {0,1}∗ be the set of all finite strings of elements from {0,1}, and let P be the class of problems recognized by deterministic Turing machines, which run in polynomial time (a problem is simply a subset of {0,1}∗). This article defines the class P ( and shows that P ( is isomorphic to the class P. Based on the notions of T-mitoticity and T-autoreducibility, K.Ambos-Spies introduced the notions of P-m-mitoticity and P-m-autoreducibility. The notions of P) -m-mitoticity and P)-m-autoreducibility are introduced by analogy with the mentioned notions. The article proves that the index sets {z | W2 is P-m-mitotic} and {z | W2 is P-m-autoreducible} are Σ3-complete.

Հրատարակիչ:

Изд-во НАН РА

Ձեւաչափ:

pdf

Նոյնացուցիչ:

oai:arar.sci.am:377895

Բնօրինակին գտնուելու վայրը:

ՀՀ ԳԱԱ Հիմնարար գիտական գրադարան