Does showing that an answer to a problem can be verified in polynomial time prove that the problem is decidable?
Here’s the scenario I have in mind: Take a finite alphabet [symbol]S[/symbol] and define a total ordering on it. Given two strings x, y in [symbol]S[/symbol]* with x < y, the goal is to find a string z in [symbol]S[/symbol]* with yz < xz.
Now, given three strings x, y, z in [symbol]S[/symbol]*, it’s very easy to determine in linear time whether x < y and xz > yz. Does that imply that an algorithm to solve the original problem will always terminate?
Unless you know more about < than just that it’s a total ordering, I don’t see why this should terminate. If < is lexicographic, for example, then x<y implies xz<yz for all z, so you’ll never find an answer.
If, on the other hand, you can prove that a solution z exists (for a given x, y, <), then you can just enumerate the strings until you find a solution.
Does this make sense, or am I completely confused?
That’s not true, unless we’re using different definitions of lexicograhic. Take [symbol]S[/symbol] as the standard ASCII alphabet with the normal ordering, x = “Toccata and Fugue in D Minor”, y = “Toccata and Fugue in D Minor (‘Dorian’)”, and z = " (J. S. Bach)" and you have a counterexample.
It looks to me like the ordering is defined on the alphabet, not on the strings. But if that’s the case, then the logical assumption for the ordering on the strings is lexicographic, which (as Omphaloskeptic says) would imply that no solution exists. And, of course, if you set yourself to naïvely searching an infinite space for something which does not exist, your search won’t terminate.
Looking at your response, ultrafilter, it seems like the answer is always that z does not exist, or there are an infinite number of them (real number infinite).
If x comes before y because y = x + a, where ‘+’ is simply a concatenation not any implied addition, then you have the example you suggest. So long as z comes after a, then (x + a + z) which is y + z comes before (x + z) for the same reason.
If you have finite-length strings, then you are left with
y = x + a, y not longest string, solution guaranteed, select any z such that z comes after a
y = x + a, y longest string, possible only if there is a string z that comes after a and that the concatenation of y + z yields simply y (because y is alreafy as long as it can be). I don’t know how to approach it if the concatenation yields some other result when y is the greatest number of possible symbols.
y != x + a, then there is no solution for the reasons already given.
In this system, 10 would be ordered before 100, with “a” = 0. Let z be the next symbol after a, ‘1’. x+z = 101, y+z = 1001, and this should result in the reverse ordering of 1001, 101.
Another example, let x = 12, let y = 123. Ordering is 12, 123, because 1=1, 2=2, and ‘’ comes before ‘3’. Here choose any z such that 3 comes before z: say, 4. x+z = 124, y+z = 1234, ordering is now 1234, 124: 1=1, 2=2, 3 comes before 4, no need for further comparison.
For any given pair of strings, there’s either no answer or infinitely many (although only a countable number).
In fact, there’s a case where it’s easy to find an answer: If y = xv, and v[sub]0[/sub] is not the maximum character, pick any c with c > v[sub]0[/sub] and yc < xc.
Also, please keep in mind that the focus of this thread is not meant to be whether this problem is ever solvable, but whether the verifiability of it implies decidability.
Oops, you’re right. But I still think that unless you know something more about < then you have to perform an enumeration of z to search, which will terminate if and only if there actually is a solution.
(Leaving aside the lexicographic example. That’s either trivial or poorly stated.)
Let the question be: does there exist a sequence of configurations* of a given Tm M on an input X that halts? Given such a sequence of configurations, verifying it is correct is trivial. Finding such a sequence is the Halting Problem which is not decidable.
*A configuration of a Tm is the encoding of the whole state of the machine: non-empty tape, state and head position.
What about this: verifiability implies that given Turing machine M, input x, and output y, there is a Turing machine M’(M,x,y) that decides M(x) = y. We can construct Turing machine N as follows:
for all y, return 1 if M’(M,x,y)
This halts because y must have finite length (or M’ would not be decidable) and there are a finite number of strings of that length or less.
ftg, correct me if I’m wrong, but if we know that a computation exists such that M(x) halts, then we can find that computation by by enumerating all computations of length 1, length 2, …, length k. Right? It’s not the halting problem because we already know that a halting computation exists.
It’s been a while since I touched any computability theory, but I’ll give it a shot.
Assume you have a boolean function f that takes two parameters that runs in polynomial time. Given x, you want to find z such that f(x, z) is true. Then, the following will always return a solution if there is one:
exhaustive_search(f, x)
{
for all z in S*
if (f(x, z)) return z
}
However, if there is no solution, then exhaustive_search will not terminate. That does not guarantee that there isn’t a different algorithm which will also terminate if there is a solution. However, my guess is there isn’t one.