LFP - shortest path problem

Curious question:

Can anyone show me how to describe shortest path problem using LFP + first order logic?

I am just getting lost on how to describe the problem, though I know that LFP + first-order logic matches to the complexity class $P$.

Thanks.

-

It is only known to match $\mathsf{P}$ on ordered structures. On unordered structures the language is quite week (and IIRC provably cannot even count, e.g. cannot state that two vertices have the same number of neighbors.)

In the presence of order it is not difficult to solve the problems: we can use the a relation to encode the computation of an arbitrary polynomial time machine (and this can be expressed in $\mathsf{FO}$ which corresponds to $\mathsf{AC^0}$) and then use $\mathsf{LFP}$ to find that relation that would satisfy this formula, but usually there is simpler way.

I am not sure what you mean by "shortest path problem" exactly. I interepret it as $$\{\langle E,s,t,k \rangle \mid \text{ the length of the shortest path from s to t in G is k }\}$$

In presence of order, we can express this as follows:

Define $\varphi(E,R)$ as $$\forall x,y,i \ \left[R(x,y,i) \leftrightarrow \left(0=i \land x=y) \lor (0<i \land \exists z \ E(x,z) \land R(z,y,i-1)\right)\right]$$ Then $\mathsf{LFP}_R(\varphi(R,E))(s,t,k)$ is true if there is a path of length at most $k$ from $s$ to $t$. The shortest path problem is then given by $$\mathsf{LFP}_R(\varphi(R,E))(s,t,k) \land \lnot \mathsf{LFP}_R(\varphi(R,E))(s,t,k-1)$$

Other versions of the shortest path problem can be solved in a similar fashion.

-