Non-wellfounded parsimonious proofs and non-uniform complexity
<|reference_start|>Non-wellfounded parsimonious proofs and non-uniform complexity: In this paper we investigate the complexity-theoretical aspects of cyclic and non-wellfounded proofs in the context of parsimonious logic, a variant of linear logic where the exponential modality ! is interpreted as a constructor for streams over finite data. We present non-wellfounded parsimonious proof systems capturing the classes $\mathbf{FPTIME}$ and $\mathbf{FP}/\mathsf{poly}$. Soundness is established via a polynomial modulus of continuity for continuous cut-elimination. Completeness relies on an encoding of polynomial Turing machines with advice.   As a byproduct of our proof methods, we establish a series of characterisation results for various finitary proof systems.<|reference_end|>
@article{acclavio2024non-wellfounded,
    title={Non-wellfounded parsimonious proofs and non-uniform complexity},
    author={Matteo Acclavio, Gianluca Curzi, Giulio Guerrieri},
    journal={arXiv preprint arXiv:2404.03311},
    year={2024},
    archivePrefix={arXiv},
    eprint={2404.03311},
    primaryClass={cs.LO}
}