The Computational Complexity of Propositional Cirquent Calculus
Introduced in 2006 by Japaridze, cirquent calculus is a refinement of sequent calculus. The advent of cirquent calculus arose from the need for a deductive system with a more explicit ability to reason about resources. Unlike the more traditional proof-theoretic approaches that manipulate tree-like...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Logical Methods in Computer Science e.V.
2015-03-01
|
| Series: | Logical Methods in Computer Science |
| Subjects: | |
| Online Access: | https://lmcs.episciences.org/1127/pdf |
| _version_ | 1797268610771582976 |
|---|---|
| author | Matthew Steven Bauer |
| author_facet | Matthew Steven Bauer |
| author_sort | Matthew Steven Bauer |
| collection | DOAJ |
| description | Introduced in 2006 by Japaridze, cirquent calculus is a refinement of sequent
calculus. The advent of cirquent calculus arose from the need for a deductive
system with a more explicit ability to reason about resources. Unlike the more
traditional proof-theoretic approaches that manipulate tree-like objects
(formulas, sequents, etc.), cirquent calculus is based on circuit-style
structures called cirquents, in which different "peer" (sibling, cousin, etc.)
substructures may share components. It is this resource sharing mechanism to
which cirquent calculus owes its novelty (and its virtues). From its inception,
cirquent calculus has been paired with an abstract resource semantics. This
semantics allows for reasoning about the interaction between a resource
provider and a resource user, where resources are understood in the their most
general and intuitive sense. Interpreting resources in a more restricted
computational sense has made cirquent calculus instrumental in axiomatizing
various fundamental fragments of Computability Logic, a formal theory of
(interactive) computability. The so-called "classical" rules of cirquent
calculus, in the absence of the particularly troublesome contraction rule,
produce a sound and complete system CL5 for Computability Logic. In this paper,
we investigate the computational complexity of CL5, showing it is
$\Sigma_2^p$-complete. We also show that CL5 without the duplication rule has
polynomial size proofs and is NP-complete. |
| first_indexed | 2024-04-25T01:35:13Z |
| format | Article |
| id | doaj.art-1d8d548c298f4187b0cd1094e3b19d98 |
| institution | Directory Open Access Journal |
| issn | 1860-5974 |
| language | English |
| last_indexed | 2024-04-25T01:35:13Z |
| publishDate | 2015-03-01 |
| publisher | Logical Methods in Computer Science e.V. |
| record_format | Article |
| series | Logical Methods in Computer Science |
| spelling | doaj.art-1d8d548c298f4187b0cd1094e3b19d982024-03-08T09:38:50ZengLogical Methods in Computer Science e.V.Logical Methods in Computer Science1860-59742015-03-01Volume 11, Issue 110.2168/LMCS-11(1:12)20151127The Computational Complexity of Propositional Cirquent CalculusMatthew Steven BauerIntroduced in 2006 by Japaridze, cirquent calculus is a refinement of sequent calculus. The advent of cirquent calculus arose from the need for a deductive system with a more explicit ability to reason about resources. Unlike the more traditional proof-theoretic approaches that manipulate tree-like objects (formulas, sequents, etc.), cirquent calculus is based on circuit-style structures called cirquents, in which different "peer" (sibling, cousin, etc.) substructures may share components. It is this resource sharing mechanism to which cirquent calculus owes its novelty (and its virtues). From its inception, cirquent calculus has been paired with an abstract resource semantics. This semantics allows for reasoning about the interaction between a resource provider and a resource user, where resources are understood in the their most general and intuitive sense. Interpreting resources in a more restricted computational sense has made cirquent calculus instrumental in axiomatizing various fundamental fragments of Computability Logic, a formal theory of (interactive) computability. The so-called "classical" rules of cirquent calculus, in the absence of the particularly troublesome contraction rule, produce a sound and complete system CL5 for Computability Logic. In this paper, we investigate the computational complexity of CL5, showing it is $\Sigma_2^p$-complete. We also show that CL5 without the duplication rule has polynomial size proofs and is NP-complete.https://lmcs.episciences.org/1127/pdfcomputer science - logic in computer science |
| spellingShingle | Matthew Steven Bauer The Computational Complexity of Propositional Cirquent Calculus Logical Methods in Computer Science computer science - logic in computer science |
| title | The Computational Complexity of Propositional Cirquent Calculus |
| title_full | The Computational Complexity of Propositional Cirquent Calculus |
| title_fullStr | The Computational Complexity of Propositional Cirquent Calculus |
| title_full_unstemmed | The Computational Complexity of Propositional Cirquent Calculus |
| title_short | The Computational Complexity of Propositional Cirquent Calculus |
| title_sort | computational complexity of propositional cirquent calculus |
| topic | computer science - logic in computer science |
| url | https://lmcs.episciences.org/1127/pdf |
| work_keys_str_mv | AT matthewstevenbauer thecomputationalcomplexityofpropositionalcirquentcalculus AT matthewstevenbauer computationalcomplexityofpropositionalcirquentcalculus |