Metatheory for Computational Complexity Theory

(Logic, English)

omplexity theory is a young science which appeared from the cooperation of mathematical logic and computer science. It studies classes of the computational complexity -- sets of decision problems that can be solved using similar amount of computational power (units of memory) and time resources. These classes are connected into a multileveled branching hierarchy with some problematic places (such as famous P versus NP problem). Every complexity class has an according logical formal system which represents formal tools needed to solve the problems from this particular class. For each class this logical formal system is different which makes relations between classes quite problematic.

Formal logic is also famous for building metatheories for formal systems since Russell's and Whitehead's project for mathematics. It is possible to build a special logical formal system not as an according system for a particular complexity class but rather as a metatheory for the entire hierarchy. "Principia Mathematica" shows that relatively simple propositional logic can serve for purpose of modeling many different areas of mathematics which are different from each other just like complexity classes are.

For these purposes certain modification of the propositional modal logic can suite as a good candidate. Modal semantics is intuitively good model for such an hierarchy as worlds represent particular classes and varying accessibility relation specifies the relations between classes implying the according modal operators. Epistemic logic may be the alternative candidate as the knowledge operator is a good representation of oracle-strings in Turing Machines for example. However general modal logic can be better for global hierarchy case when epistemic logic serves better for local cases.

The problem with applicability of modal semantics to complexity theory case concerns the completeness and soundness of such a formal system.

Chair: Tobias Koch

Time: 14:40-15:10, 14 September 2018 (Friday)

Location: SR 1.006

Iaroslav Petik

(Institute of Philosophy of the Academy of Sciences of Ukraine, Ukraine)

Born in Russia 1992.

Moved to Ukraine a year later, a citizen of Ukraine.

BA and MA in philosophy, currently a PhD student in philosophy (specialization: logic).

© 2021 SOPhiA. All rights reserved.
Last update: 2014-04-01.