@inproceedings{fc288fd5835d49cca6083f8070fd7755,
title = "Uniform circuits, & Boolean proof nets",
abstract = "The relationship between Boolean proof nets of multiplicative linear logic (APN) and Boolean circuits has been studied [Ter04] in a non-uniform setting. We refine this results by taking care of uniformity: the relationship can be expressed in term of the (Turing) polynomial hierarchy. We give a proofs-as-programs correspondence between proof nets and deterministic as well as non-deterministic Boolean circuits with a uniform depth-preserving simulation of each other. The Boolean proof nets class m&BN(poly) is built on multiplicative and additive linear logic with a polynomial amount of additive connectives as the non-deterministic circuit class NNC (poly) is with non-deterministic variables. We obtain uniform-APN = NC and m&BN(poly) = NNC(poly) = NP.",
author = "Virgile Mogbil and Vincent Rahli",
year = "2007",
doi = "10.1007/978-3-540-72734-7_28",
language = "English",
isbn = "3540727329",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "401--421",
booktitle = "Logical Foundations of Computer Science. LFCS 2007",
note = "International Symposium on Logical Foundations of Computer Science 2007, LFCS 2007 ; Conference date: 04-06-2007 Through 07-06-2007",
}