Decision problems

Warning : This page is under construction. 

Provability problem

MLL = Multiplicative Linear Logic
MALL = Multiplicative Additive Linear Logic
MELL = Multiplicative Exponential Linear Logic
LL = Linear Logic

NP = non deterministic polynomial time
PSPACE = polynomial space
NEXPTIME = non deterministic exponential time
 
 
MLL
MALL
MELL
LL
propositional case
NP-complete
PSPACE-complete
unknown
undecidable
first order case
NP-complete
NEXPTIME-complete
undecidable
undecidable
second order case
undecidable
undecidable
undecidable
undecidable