I consider declarative and procedural to be readings of a program (i.e, a subjective property). A more interesting property is amenability to formal reasoning,

I consider declarative and procedural to be readings of a program (i.e, a subjective property). A more interesting property is amenability to formal reasoning, which is what is really wanted. A distinction from functional programming can be made by noting that in functional programming the input is a proof term, and in logic programming the output is a proof term (evaluation is proof search). But excluding optimized domain-specific solvers which are making performance/expressiveness/termination tradeoffs, it doesn't seem obvious that programming via proof search has any definite complexity disadvantages in theory (assuming you encode the algorithm in a comparable way), though I admit in practice the existing implementations of logic programming are anemic when it comes to libraries, polish, etc.