All Questions
Tagged with structural-complexity probabilistic-complexity
1 question
5
votes
0
answers
1k
views
Any known connections between open problems for time and space: P vs L, NP vs NL, BPP vs BPL, ⊕P vs ⊕L
It would be nice to show that $P=L$ implies $NP=NL$. Or, $NP=NL$ implies $UP=UL$. Or maybe, $⊕P = ⊕L$ implies $PP = PL$.
Are there any known connections between the problems: P vs L, UP vs UL, NP ...
- 5,167