Logo do repositório
 
Publicação

A Recursion-Theoretic Characterization of the Probabilistic Class PP

2021-08-01Documento de conferência Acesso aberto
Ver registo simples
dc.contributor.authorDal Lago, Ugo
dc.contributor.authorKahle, Reinhard
dc.contributor.authorOitavem, Isabel
dc.contributor.institutionCMA - Centro de Matemática e Aplicações
dc.contributor.institutionDM - Departamento de Matemática
dc.date.accessioned2022-02-03T23:32:56Z
dc.date.available2022-02-03T23:32:56Z
dc.date.issued2021-08-01
dc.descriptionANR Project PPS 19CE480014
dc.description.abstractProbabilistic complexity classes, despite capturing the notion of feasibility, have escaped any treatment by the tools of so-called implicit-complexity. Their inherently semantic nature is of course a barrier to the characterization of classes like BPP or ZPP, but not all classes are semantic. In this paper, we introduce a recursion-theoretic characterization of the probabilistic class PP, using recursion schemata with pointers.en
dc.description.versionpublishersversion
dc.description.versionpublished
dc.format.extent721186
dc.identifier.doi10.4230/LIPIcs.MFCS.2021.35
dc.identifier.isbn9783959772013
dc.identifier.issn1868-8969
dc.identifier.otherPURE: 34087592
dc.identifier.otherPURE UUID: b5fd2805-7ca8-48a2-83c3-acbd0642ed5a
dc.identifier.otherScopus: 85115437962
dc.identifier.otherORCID: /0000-0002-9064-877X/work/107609313
dc.identifier.urihttp://hdl.handle.net/10362/132224
dc.identifier.urlhttps://www.scopus.com/pages/publications/85115437962
dc.language.isoeng
dc.peerreviewedyes
dc.publisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
dc.relationinfo:eu-repo/grantAgreement/EC/H2020/818616/EU
dc.relationDifferential Program Semantics
dc.relationCenter for Mathematics and Applications
dc.subjectImplicit complexity
dc.subjectPolynomial time
dc.subjectPp
dc.subjectProbabilistic classes
dc.subjectTree-recursion
dc.subjectSoftware
dc.titleA Recursion-Theoretic Characterization of the Probabilistic Class PPen
dc.typeconference object
degois.publication.title46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021
degois.publication.title46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021
dspace.entity.typePublication
oaire.awardNumber818616
oaire.awardNumberUIDB/00297/2020
oaire.awardTitleDifferential Program Semantics
oaire.awardTitleCenter for Mathematics and Applications
oaire.awardURIinfo:eu-repo/grantAgreement/EC/H2020/818616/EU
oaire.awardURIinfo:eu-repo/grantAgreement/FCT/6817 - DCRRNI ID/UIDB%2F00297%2F2020/PT
oaire.fundingStreamH2020
oaire.fundingStream6817 - DCRRNI ID
project.funder.identifierhttp://doi.org/10.13039/501100008530
project.funder.identifierhttp://doi.org/10.13039/501100001871
project.funder.nameEuropean Commission
project.funder.nameFundação para a Ciência e a Tecnologia
rcaap.rightsopenAccess
relation.isProjectOfPublication03f0e9f9-363e-4803-9d1d-3d73f558279a
relation.isProjectOfPublicationd00ae22f-ec2b-47b2-935e-60cb44493cc6
relation.isProjectOfPublication.latestForDiscovery03f0e9f9-363e-4803-9d1d-3d73f558279a

Ficheiros

Principais
A mostrar 1 - 1 de 1
Miniatura
Nome:
LIPIcs_MFCS_2021_35.pdf
Tamanho:
704.28 KB
Formato:
Adobe Portable Document Format
Ver/Abrir

Coleções

FCT: DM - Documentos de conferências internacionais