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 
NPcomplete

PSPACEcomplete

unknown

undecidable

first order case 
NPcomplete

NEXPTIMEcomplete

undecidable

undecidable 
second order case 
undecidable

undecidable

undecidable

undecidable
