Publication:
On pure space vs catalytic space

Simple item page
cris.virtual.department#PLACEHOLDER_PARENT_METADATA_VALUE#
cris.virtual.department#PLACEHOLDER_PARENT_METADATA_VALUE#
cris.virtual.departmentIndian Institute of Technology, Madras
cris.virtualsource.department#PLACEHOLDER_PARENT_METADATA_VALUE#
cris.virtualsource.department#PLACEHOLDER_PARENT_METADATA_VALUE#
cris.virtualsource.departmente532bd8d-54bf-4c4e-84e0-a2f7b9463ceb
dc.contributor.authorBisoyi, Sagar
dc.contributor.authorDinesh, Krishnamoorthy
dc.contributor.authorJayalal Sarma
dc.date.accessioned2023-09-19T14:10:00Z
dc.date.available2023-09-19T14:10:00Z
dc.date.issued19-06-2022
dc.description.abstractThis paper explores the power of catalytic computation when the catalytic space (c(n), the full memory whose content needs to be restored to the original by the end of computation) is much more than exponential in the pure space (s(n), the empty memory which does not have any access/restoration constraints). We study the following three regimes of the relation between s(n) and c(n) and explore the class CSPACE(s(n),c(n)) in each of them. • High-end regime - s(n)=O(c(n)ϵ): We show an implementation of incremental dynamic program using catalytic machines, thus showing that Knapsack problem (with n items, sum of their costs as C and the capacity of the bag as K) can be solved in O(nlog⁡nlog⁡C+log⁡(nKC)) pure space and O(n2KC3log2⁡Klog⁡n) catalytic space. Hence, catalytic algorithms can lead to a non-trivial saving in the pure space required for computation when K is Ω(n2). • Low-end regime - s(n)=O(1): We define the classes CR and CNR (nondeterministic variant of CR) where s(n)=O(1) and c(n)=poly(n). Exploring the connection between computational power of one counter machines (OC) and constant pure space catalytic Turing machines, we observe that OC⊆CR and show that CR⊆OC⇒CR≠CNR. We prove that L⊈CSPACE(O(1),o(n)). We also study the effect of adding additional read-only tapes to the model and show that: For any k∈N, (k+1)-CSPACE(O(1),O(nc))⊆CSPACE(klog⁡n,nc)⊆(4k+1)-CSPACE(O(1),O(nc)). • Low-end non-constant regime - s(n)=o(log⁡log⁡n): Let M be an oblivious catalytic Turing machine using s(n) pure space and c(n) catalytic space such that s(n)+log⁡c(n)=o(log⁡log⁡n) then L(M) is regular. This strengthens the classical theorem on s(n)=o(log⁡log⁡n) to the case of catalytic Turing machines. Our techniques include interesting generalizations of crossing sequence arguments and implementations of incremental dynamic programs using catalytic algorithms. These may be of independent interest.
dc.identifier.doi10.1016/j.tcs.2022.04.005
dc.identifier.issn3043975
dc.identifier.scopus2-s2.0-85128162973
dc.identifier.urihttps://apicris.irins.org/handle/IITM2023/26448
dc.relation.ispartofseriesTheoretical Computer Science
dc.sourceTheoretical Computer Science
dc.subjectCatalytic computation
dc.subjectCrossing sequence
dc.subjectKeywords space complexity
dc.subjectLower bounds
dc.titleOn pure space vs catalytic space
dc.typeJournal
dspace.entity.typePublication
oaire.citation.endPage126
oaire.citation.startPage112
oaire.citation.volume921
oairecerif.author.affiliation#PLACEHOLDER_PARENT_METADATA_VALUE#
oairecerif.author.affiliation#PLACEHOLDER_PARENT_METADATA_VALUE#
oairecerif.author.affiliationIndian Institute of Technology, Madras
person.affiliation.cityChennai
person.affiliation.cityHong Kong
person.affiliation.id60025757
person.affiliation.id60002798
person.affiliation.nameIndian Institute of Technology Madras
person.affiliation.nameChinese University of Hong Kong
person.identifier.scopus-author-id57217133849
person.identifier.scopus-author-id57193091648
person.identifier.scopus-author-id23092218300
Files
Collections
Publication1