Назад до архіву

Випуск №31 2018

[текст статті] - PDF

https://doi.org/10.17721/2521-6805.2018/31-9/11

 

УДК 35.088.6

Я. О. Петік, аспірант

Інституту філософії імені Г.С. Сковороди

Академії Наук України, Київ, Україна

e-mail: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.

ORCID 0000-0002-6127-5943

 

ЛОГІКА ОБЧИСЛЮВАЛЬНОЇ СКЛАДНОСТІ

 

Побудовано семантику логічної модальної метатеорії для дослідження класів алгоритмічної складності. Досліджується ефективність цього числення на прикладі розгляду відомої проблеми класів алгоритмічної складності – питання про рівність класів P та NP. Розроблено новий теоретико-методологічний підхід до цієї проблеми. Розроблено оригінальну семантику модальної логіки, яку можна застосовувати для опису структурних відношень між різноманітними класами алгоритмічної складності з теорії алгоритмічної складності. На основі цієї семантики можна розробити повноцінне числення логіки алгоритмічної складності. Уперше було застосовано модальну логіку до дослідження відносин між класами алгоритмічної складності. Розроблено нові теоретично-методологічні підходи до класичних проблем теорії алгоритмічної складності. Робота має значення для кібернетики, філософії математики, логіки, теорії алгоритмів, криптографії.

Ключові слова: модальна логіка, метатеорія, обчислювальна складність, алгоритм, P та NP.

 

Я. О. Петик, асп.

Институт философии имени Г.С. Сковороды

Академии Наук Украины, Киев, Украина

 

ЛОГИКА ВЫЧИСЛИТЕЛЬНОЙ СЛОЖНОСТИ

 

Разработана семантика логической модальной метатеории для исследования классов алгоритмической сложности. Исследуется эффективность данного исчисления на примере рассмотрения известной проблемы классов алгоритмической сложности – вопроса про равенство классов Р и NP. Разработан новый теоретикометодологический подход к этой проблеме. Была разработана оригинальная семантика модальной логики, которую можно использовать для исследования структурных отношений между классами алгоритмической сложности. На основе этой семантики в будущем можно разработать полноценное исчисление логики алгоритмической сложности. Впервые была использована модальная логика для исследования отношений между классами алгоритмической сложности. Разработаны новые теоретико-методологические подходы к классическим проблемам теории алгоритмической сложности. Работа имеет значение для кибернетики, философии математики, логики, теории алгоритмоф, криптографии.

Ключевые слова: модальная логика, метатеория, вычислительная сложность, алгоритм, P и NP.

 

Список використаних джерел:

1. Клини С. Математическая логика. / С. Клини. Москва, ЛКИ, 2008. 482 с.

2. Мендельсон Э. Введение в математическую логику. / Э. Мендельсон. Москва, Наука, 1971. – 320 с.

3. Arora S., Barak B. Computational Complexity: A Modern Approach. / S. Arora, B. Barak. Cambridge, Cambridge University Press, 2007. - 473 P.

4. Givant Steven. Bibliography of Alfred Tarski / Steven Givant // Journal of Symbolic Logic. № 51. 1986. P. 913–41.

5. Goldreich O. Computational complexity: a conceptual perspective. / O. Goldreich. Cambridge University Press,  2008. 632 P.

6. Hintikka J. Knowledge and Belief: An Introduction to the Logic of the Two Notions. — Ithaca, NY, Cornell University Press, 1962. 179 P.

7. Mares, E.D., Fuhrmann A. A Relevant Theory of Conditionals / E.D. Mares, A. Furhmann // Journal of Philosophical Logic. №24. 1995.   P. 645–665.

8. Turing A. M. Computability and λ-Definability / A.M. Turing. // The Journal of Symbolic Logic. № 2. 1937. P. 153-163.

9. Whitehead A., Russell B. Principia Mathematica. / A. Whitehead, B. Russell. Cambridge, Cambridge University Press, 1910. – 680 P.

 

© Я. О. Петік

© 2018 Київський національний університет імені Тараса Шевченка