Originally posted by: Blouge
>Suppose P(x1,...,xn) is a decidable predicate in n free variables
I find your post a bit confusing. To me, "decidable" means you can make up your mind on whether the particular predicate is true or false for particular values x1...xn. Is this what you meant? Also, I'm not sure how to "solve" a predicate.
Perhaps you simply meant that the statement "P(x1,...,xn)=0" has a solution?
'Decidable' means that its characteristic function is total; that is, for any given sequence of values as argument, there is an effective procedure for determining whether *or not* that sequence satisfies the predicate. That is what I said when I said "...it could take longer than is physically feasible to determine for given values of x1,...,xn whether P(x1,...,xn) is true or false" with respect to decidability.
To "solve" for P means to provide an algorithm (effective procedure) that determines for any given sequence of values whether or not that sequence satisfies the predicate. The existence of such a solution is known as a solution to the decision problem for P. The decision problem for a predicate is a class of questions of the form "Is P(x1,...,xn) true for the values x1=a1,...,xn=an?", where each ai is a member of the elements of the domain of a given structure (possibly of the intended interpretation of P).
The statement 'P(x1,..,xn)=0' is not well-formed when P is a predicate and '=' denotes a relation between individuals, not classes of n-tuples of individuals. So no, that's not what I meant. You seem to be thinking in terms of the characteristic function of P which is defined as:
f(x1,...,xn) = {1 if P(x1,...,xn) is true; 0 otherwise.
But that is not called the 'decision problem' for P. It's the computation problem for its corresponding characteristic function.
Originally posted by: Blouge
If so, then you've tried to sweep a big problem under the rug: in practice you usually don't know if there is a solution.
That is why I restricted attention to *decidable* predicates, as I stated in my original post. Now given the class of decidable predicates, such as the deducibility relation for propositional logic (as I already mentioned), quantum computing would allow solving for very complex sequences of formulas in faster than exponential time. Suppose you have a sequence of formulas x1,...xn-1 and you want to find out whether xn is deducible from them. Moreover, suppose max(x1,..,xn)=m, so that there are 2^m rows of a truth-table to compute. If m is even relatively small, it could forever to compute. But what if we could compute every 2^m permutation of the value of the variables simultaneously?