Time complexity of Prolog better than naive brute force?

Question

Is the time complexity of solving anything in (the best) Prolog better than a naive brute force backtracking implementation?

I say the language Prolog generally... I'm wondering if there is some well known algorithm for this, that would for example make 'doing Prolog' using call/cc backtracking in Scheme a poor choice.

EDIT: by "solving anything" I mean all Prolog programs. The "question in a question": I'm wondering about language design: if full continuations have any practical utility over partial continuations (the main advantages being Prolog-esque, but which aren't serious if they can't compete on time complexity with Prolog), and also if another language could completely absorb Prolog or if there are optimizations made possible by restricting programs to a Prolog form (analogous to the optimization possible in Fortran over C).

EDIT: by time complexity I meant big O, i.e. pruning that wouldn't be possible emulating Prolog naively in a general language.

Answer 1

A naive brute force search will remain a naive brute force search when it is literally translated to Prolog.

That's OK: Plain Prolog is very well suited for describing and running brute force searches. Still, you will likely not be able to beat a hand-optimized low-level version of any brute force search with a brute force search written in Prolog. On the other hand, Prolog is so easy and convenient to type that you will likely soon find better search strategies with a bit of prototyping, and these other strategies will often easily beat any brute force implementation by a huge margin. And even when translated naively, Prolog is pretty good at backtracking and does it efficiently within some (smaller or larger, depending on the Prolog implementation you use) factor of lower-level code.

However, the key advantage that Prolog has over many other languages when describing search problems are constraints: Due to so-called constraint propagation, the search space can often be pruned significantly and automatically. No special provisions are necessary on your part: The constraint solver will do it for you.

The promise of constraints, and that promise has to a large extent turned into reality, is that (1) you state the requirements and (2) the Prolog engine finds the solution for you. Check out clpfd for one very important instance of this scheme.

I therefore suggest the question: In any language, how easy is it to convert a naive brute force search into a more informed search strategy? After all, this is how the really significant improvements typically become possible.

In Prolog, the answer is often: Very easy. In most other languages, not so much.