4
$\begingroup$

Is there a counterexample or theorem for the question below?

Examples:

Let's look at some examples first to get the feel of it. We'll let $n$ be the length of the input in characters. All the examples are recognizers that aren't intended to produce any output other than "accept" or "reject".

  1. Linear search. We're given a sequence of characters. An input character is read; if it matches what is searched for, we terminate with success. If not, that input can be thrown away since it doesn't match and we go on to the next character in the input.

  2. Deterministic context-free parsing. An input word is read and either shifted onto the stack or reduced with the existing stack, to form a new stack. Since the parser is just a recognizer, we don't have to remember the original input word once it has been reduced into a nonterminal.

  3. Final character matching. This is an artificial example to clarify the question. The format is $n-1$ input characters that don't matter and a final character that does. If the final character matches a fixed constant character, we succeed, otherwise we fail. Again, we can simply throw away all non-final characters as they're read since they don't matter.

In each case, gradual progress is being made toward a solution each time an input is read, where "gradual progress" is a gradual transformation of the machine configuration into a final state such that at some step during the transformation, enough information is lost to make it impossible to reconstruct the original input: that is, the computation becomes irreversible to the extent that it is impossible to reconstruct the original input. Is the following paragraph true for every polynomial-time recognizer? Is there a theorem to back it up? Or is there a counterexample?

Question:

(Notation: L is a language in P, and M is a polynomial-time recognizer for L.) For all L there exists an M (subject to the constraints below) where there is progress (defined above) during the computation. More precisely, there is no L in P such that for every constrained (see below) M for L there is no progress during the first $n-1$ characters of the computation and then a "sudden flash" that produces the answer on encountering the final input character.

We are given two constraints:

  1. Irreducibility. There is no polynomial-time reduction from a "sudden flash" machine to a gradual one, so we can't just create a wrapper machine which batches up the inputs and at the end simply passes it to a gradual machine to actually carry out the computation.

  2. Incompressibility. We are also given that there is no polynomial-time compression transformation of an input $n$ characters in length to a size substantially less than linear: that is, of a complexity class less than $O(n)$; see example 3 above (this gets rid of highly redundant examples).

EDIT: In one of the comments I suggested a proviso; this is no longer necessary. In the case of string matching, I mentioned that there is an algorithm which simply throws away initial characters as long as they match, thus providing irreversibility. In the case of a constant test string, I had suggested a finite-state solution, but this is not necessary since there is simply a polynomial-time reduction to the first string matching strategy in this paragraph. So the proviso I suggested is withdrawn; the question stands.

  • 0
    I fi$x$ed that; the question should be self-contained and not rely on the comments for clarification.2011-07-11

1 Answers 1

1

I hope I've now correctly understood the question as clarified in the comments. Your definitions of progress and reconstructibility are somewhat informal, but I think I see what you're getting at; please correct me if I'm still misinterpreting something.

I think a counterexample is provided by a polynomial-time recognizer of reversed initial sections of some normal sequence whose initial sections can be computed in polynomial time, for instance the decimal digits of the Champernowne constant or, presumably, the hexadecimal digits of $\pi$ ("presumably" because it's not known, though widely believed, that these form a normal sequence). In trying to decide whether a given input is such a reversed initial section, the entire input has to be stored until the end is reached, since there is no way of knowing which parts of the sequence to compare the input to before the end is reached, and all possible finite patterns occur infinitely often in a normal sequence, so it can never be excluded that what's been seen so far could be the beginning of one of the reversed initial sections; whether it is always potentially depends on a single piece of the input already seen.

  • 0
    @hardmath: ...this includes order effects that can be eliminated in polynomial time, including reversals. So the intention was to get a counterexample that maintains reversibility after withstanding all polynomial-time attempts to get rid of that reversibility. Finally, yes, the reverser cannot throw away characters in this case and still preserve a polynomial-time reduction. If my exposition is inconsistent with what I'm saying here, please let me know so I can fix it.2011-07-13