Побудовано семантику логічної модальної метатеорії для дослідження класів алгоритмічної складності. Досліджується ефективність цього числення на прикладі розгляду відомої проблеми класів алгоритмічної складності - питання про рівність класів P та NP. Розроблено новий теоретико-методологічний підхід до цієї проблеми. Розроблено оригінальну семантику модальної логіки, яку можна застосовувати для опису структурних відношень між різноманітними класами алгоритмічної складності з теорії алгоритмічної складності. На основі цієї семантики можна розробити повноцінне числення логіки алгоритмічної складності. Уперше було застосовано модальну логіку до дослідження відносин між класами алгоритмічної складності. Розроблено нові теоретично-методологічні підходи до класичних проблем теорії алгоритмічної складності. Робота має значення для кібернетики, філософії математики, логіки, теорії алгоритмів, криптографії.
The paper centers on building the semantics of the modal metatheory for studying the classes of algorithmic complexity. Further the effectiveness of this calculus is studied on the example of researching the famous problem of computational complexity theory - the question of equality of the classes P and NP. The new theoretical and methodological app&roach to the problem is provided. The original semantics was developed that can be used for description of relations between classes of algorithmic complexity from the complexity theory. On the basis of this semantics the complete calculus of the log&ic of the computational complexity can be developed in future. It is the first time when modal logic is used for studying the relations between classes of algorithmic complexity. New theoretical and methodological approaches to the classical problems& of the complexity theory are proposed. Paper matters for computer science, philosophy of mathematics, logic and theory of algorithms, cryptography.
Разработана семантика логической модальной метатеории для исследования классов алгоритмической сло&жности. Исследуется эффективность данного исчи- сления на примере рассмотрения известной проблемы классов алгоритмической сложности -вопроса про равенство классов Р и NP. Разработан новый теоретико- методологический подход к этой проблеме. Была разра&ботана оригинальная семантика модальной логики, которую можно использовать для исследования структурных отношений между классами алгори- тмической сложности. На основе этой семантики в будущем можно разработать полноценное исчисление логики алгоритми&ческой сложности. Впервые была использована модальная логика для исследования отношений между классами алгоритмической сложности. Разработаны новые теоретико- методологические подходы к классическим проблемам теории алгоритмической сложности. Работа &имеет значение для кибернетики, философии математики, логики, те- ории алгоритмоф, криптографии.
