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
|