Is there a counterexample or theorem for the question below?


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?


(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.

  • $\begingroup$ You mean example 3 above? $\endgroup$ – joriki Jul 11 '11 at 20:28
  • $\begingroup$ I'm not sure I understand the question correctly. What if we're trying to determine whether the entire input matches a certain string? At each point, the input can be reconstructed, since the fact that the process hasn't terminated implies that the input so far matched the string. Am I missing something? $\endgroup$ – joriki Jul 11 '11 at 20:39
  • $\begingroup$ @joriki: Thanks for the clarification. If one is matching against a string, one can just throw away the corresponding initial characters if they match. If the string is constant, the problem is just finite-state, so the state/configuration doesn't have to hold it. I should have added the proviso that the information is actually encoded into the machine configuration, and not just logically derivable. As for your earlier question, I'll need more explanation. Thanks $\endgroup$ – ShyPerson Jul 11 '11 at 21:12
  • $\begingroup$ I meant that in constraint 2 you say "see example 4 above" but there are only examples 1 to 3 and you seem to be referring to example 3? $\endgroup$ – joriki Jul 11 '11 at 21:20
  • $\begingroup$ @joriki: Yes, sorry, that should be example 3. Thanks $\endgroup$ – ShyPerson Jul 11 '11 at 21:26

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.

  • $\begingroup$ If I understand your answer properly, it doesn't look like it satisfies the irreducibility constraint. We can take the reversed initial section, reverse it back to its normal order in polynomial time, and pass it to a recognizer which can throw away input digits as it computes or matches against the desired sequence. $\endgroup$ – ShyPerson Jul 12 '11 at 19:35
  • $\begingroup$ @Shy Person: But wouldn't then reversing of the initial section require the "last" input character to be read, followed by passing it to a recognizer, fail the "sudden flash" criterion? Certainly the reverser is not allowed to throw away characters. $\endgroup$ – hardmath Jul 12 '11 at 21:38
  • $\begingroup$ @hardmath: Thanks for asking; maybe I messed up my exposition. First, the whole issue around the final character was to cover the problem that when the algorithm sees the final character, it can erase all the inputs because it can then determine whether to accept or reject; banning the final character gets around this problem, at least to some extent. Second, the irreducibility constraint was intended to make the reversibility of any candidate counterexample intrinsic to the counterexample problem itself rather than peripheral effects; ... $\endgroup$ – ShyPerson Jul 13 '11 at 15:58
  • $\begingroup$ @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. $\endgroup$ – ShyPerson Jul 13 '11 at 15:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.