theoretical-cs

[pure lake]

regardless this is a nothingburger sorry for wasting time

[willow wedge]

Assume SUBEXP = PSPACE and EXP = PSPACE
Then SUBEXP = EXP, contra time hierarchy, no? So you could prove anything in that case 😅

I think that's the main sticking point, SUBEXP and EXP are already separated

[pure lake]

Exactly, that means that SUBEXP = PSPACE -> EXP != PSPACE

my idea was proof by contradiction showing that SUBEXP = PSPACE -> EXP != PSPACE and SUBEXP != PSPACE -> EXP != PSPACE, therefore EXP != PSPACE

the SUBEXP != PSPACE -> EXP != PSPACE almost, gets tantalizingly close to working

but that splits into 2 possibilities, either PSPACE contains SUBEXP or it doesn't contain SUBEXP

if PSPACE doesnt contain SUBEXP you get a trivial contradiction, because SUBEXP is contained strictly within EXP, that means that there is a problem in EXP not in PSPACE, so PSPACE != EXP

The thing is, we also need to acount for PSPACE containing SUBEXP which seems unlikely but a P vs NP type seperation

but like there should intuitionally be some problem in SUBEXPSPACE that needs at least SUBEXPSPACE that can also be solved in SUBEXPTIME

so this reduces to SUBEXP vs SUBEXPSPACE

if SUBEXP = SUBEXPSPACE then this is trivial

if SUBEXP != SUBEXPSPACE then uhh

fun