Does ((L=NP) and (PH=PSPACE)) imply (FO=SO)? Is (L=/=NP) or (PH=/=PSPACE)?

47 Views Asked by At

First-order logic with a commutative, transitive closure operator added yields SL, which equals L, problems solvable in logarithmic space.

[1] L = FO with commutative transitive closure operator.

Second-order logic with a transitive closure (commutative or not) yields PSPACE, the problems solvable in polynomial space.

[2] PSPACE = SO with transitive closure operator.

[3] (L=NP) implies (P=NP).

[4] (P=NP) implies (collapse of PH).

[5] ((Collapse of PH) and (L=NP)) implies L=PSPACE.

[6] L=PSPACE implies (FO with commutative transitive closure operator) = (SO with transitive closure operator).

[7] ((FO with commutative transitive closure operator) = (SO with transitive closure operator)) implies (FO = SO)

Does ((L=NP) and (PH=PSPACE)) imply (FO=SO)?

I'm not sure about [7]; This seems to contradict "Second-order logic is more expressive than first-order logic."

(Even if [7] is false) does (FO with commutative transitive closure operator) =/= (SO with transitive closure operator) imply ((L=/=NP) or (PH=/=PSPACE))?

2

There are 2 best solutions below

1
On

L $\not=$ PSPACE due to the space hierarchy theorem. So L=NP or PH=PSPACE is false.

0
On

We also have a separation between $\textsf{FO}$ and $\textsf{SO}$. Note that:

$$\textsf{FO} = \textsf{AC}^{0} \subsetneq \textsf{ACC}^{0} \subseteq \textsf{TC}^{0} \subseteq \textsf{NC}^{1} \subseteq \textsf{L}.$$

On the other hand, $\textsf{SO} = \textsf{PH}$. So $\textsf{FO} \subsetneq \textsf{SO}$.