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

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

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

2020

Հատոր:

53

ISSN:

2579-2784

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

Պետրոսյան Գարիկ Վ., Петросян Гарик В.

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

Արտածման բարդությունների բազմանդամային սահմանափակումներ ԴՆՁ նույնաբանությունների որոշակի դասերի համար; Полиномиальное ограничение сложностей выводов некоторых классов ДНФ-тавтологий

Ծածկույթ:

7-13

Ամփոփում:

In this paper, we present the results on Frege proof complexities of some DNFtautologies. At first we introduce the notion of complete DNFs and prove that complete DNFs are tautologies, we also show that if the proof complexities for the set of complete DNFs are polynomially bounded, then the set of DNF-tautologies D, for which the number of non-negated variables in every conjunct is O(log(D)), also has polynomially bounded proof complexities. Later we show that the set of all balanced DNF-tautologies has polynomial proof complexities. Սույն հոդվածում հետազոտվել են ԴՆՁ նույնաբանությունների որոշ դասերի արտածման բարդությունները Ֆրեգե համակարգերում: Ներմուծվել է լրիվ ԴՆՁ-ների հասկացությունը և ցույց է տրվել, որ լրիվ ԴՆՁ-ները նույնաբանություններ են: Ապացուցվել է, որ եթե լրիվ ԴՆՁ-ների բազմությունը բազմանդամորեն սահմանափակ արտածելի է, ապա բոլոր այն D ԴՆՁ-նույնաբանությունների բազմությունը, որի տարրերի յուրաքանչյուր կոնյունկտում առանց ժխտման հանդես եկող փոփոխականների քանակը O( log( jDj) ) է ևս բազմանդամորեն սահմանափակ արտածելի է: Ապացուցվել է նաև, որ բալանսավորված ԴՆՁ-նույնաբանությունների որոշակի դաս նույնպես բազմանդամորեն սահմանափակ արտածելի է: В этой статье исследованы сложности выводов в системах Фреге для некоторых классов ДНФ-тавтологий. Введено понятие полных ДНФ и доказано, что полные ДНФ являются тавтологиями и, если множество полных ДНФ имеет полиномиально ограниченные сложности выводов, то множество всех ДНФ тавтологий D в каждом конъюнкте которых число неотрицательных переменных является O( log( jDj) ) , также имеет полиномиально ограниченные сложности выводов. Далее доказано, что некоторый класс сбалансированных ДНФ тавтологий также имеет полиномиально ограниченные сложности выводов.

Հրատարակիչ:

Изд-во НАН РА

Ձևաչափ:

pdf

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

oai:arar.sci.am:261601

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

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