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= NCand m& BN(poly) = NNC(poly)=NP. |
Year | DOI | Venue |
---|---|---|
2007 | 10.1007/978-3-540-72734-7_28 | LFCS |
Keywords | Field | DocType |
boolean proof nets class,proof net,additive connective,boolean proof nets,ncand m,non-deterministic boolean circuit,boolean proof net,additive linear logic,non-deterministic variable,non-deterministic circuit class,boolean circuit,uniform circuits,boolean circuits,linear logic | Cook–Levin theorem,Karp–Lipton theorem,Discrete mathematics,Combinatorics,Boolean circuit,Parity function,Product term,Boolean algebra,Boolean expression,Two-element Boolean algebra,Mathematics | Conference |
Volume | ISSN | Citations |
4514 | 0302-9743 | 2 |
PageRank | References | Authors |
0.43 | 14 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Virgile Mogbil | 1 | 69 | 6.77 |
Vincent Rahli | 2 | 43 | 9.21 |