フラグメントによる非古典論理の複雑さのモデル化

この論文は、非古典論理（超直観主義論理と様相論理）の計算複雑性を、より単純なフラグメントへの多項式時間還元によって探求しています。これは、より扱いやすいサブセットを研究することによって、複雑な論理システムを分析できるため重要です。この発見は、新しい複雑さの境界と、これらの還元の限界に関する洞察を提供し、これらの論理のより深い理解に貢献しています。

• •命題論理と述語論理のより単純なフラグメントへの多項式時間還元を実証。
• •いくつかの論理に対する新しい複雑さの境界を提供。
• •述語計算のクリプケ不完全性を調査。
• •準二項述語に対するチャーチとトラクテンブロートの定理のアナログを提供。