Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.