4
$\begingroup$

The complexity class NL seems to allow cycling, otherwise we wouldn't have SL $\subset$ NL. What about L? If an algorithm from L cycles for a given input, it certainly cannot accept (because it won't enter the accepting state), so we could define that it rejects in this case (which would be consistent with NL). Or is cycling simply not allowed for L?

Does this makes any difference at all, i.e. would NL or L get weaker (in the sense that we can't prove that they still accept the same languages), if we would completely forbid cycling?

$\endgroup$
  • 6
    $\begingroup$ What do you mean by "cycling"? Do you mean that the TM repeats a configuration? If so, it can always be avoided by keeping a (logspace) counter for the maximal number of configurations, and halting when the counter resets. $\endgroup$ – Shaull Feb 16 '16 at 10:42
  • 1
    $\begingroup$ @Shaull Exactly. The idea with the counter answers this question. So one can allow or forbid cycling on a case by case decision, whatever is more convenient for the specific case. $\endgroup$ – Thomas Klimpel Feb 16 '16 at 11:32
  • $\begingroup$ I do not understand why you seem to claim that an NDTM deciding (for instance) STCON must cycle. Yes, for a YES instance there will be accepting runs where a configuration is repeated if one uses a trivial NDTM that tracks the current vertex and guesses which successor to go to next. However, there is then always an accepting run without a repeated configuration, by removing the parts of the run that loop. In other words, if there is an accepting run, then there is an accepting run that does not repeat the machine configuration. Could you clarify? $\endgroup$ – András Salamon Feb 17 '16 at 7:11
  • $\begingroup$ @AndrásSalamon You may also interpret "NL seems to allow cycling" as "it seems that we may allow NL to contain machines which cycle for certain inputs". The reasoning behind the entire sentence is simple. If allowing cycling for NL would be problematic, this issue would be discussed in much more detail when talking about SL $\subset$ NL. The straightforward definition of SL involves machines for which cycling is the rule rather than the exception. $\endgroup$ – Thomas Klimpel Feb 17 '16 at 8:53
  • $\begingroup$ I still do not understand your contention. If there is an accepting run of an NDTM, then there is an accepting run that does not repeat any machine configuration. SL is contained in NL because it imposes an additional condition on the transition relation of the NDTM. Where is the cycling? $\endgroup$ – András Salamon Feb 17 '16 at 9:40
1
$\begingroup$

Shaull's comment answers the question:

Do you mean that the TM repeats a configuration? If so, it can always be avoided by keeping a (logspace) counter for the maximal number of configurations, and halting when the counter resets.

This technique can even be used, without knowing (beforehand) any bound for the amount of space used. The TM can just keep track of the amount of space used till the current step (excluding the additional counter), and halt when the counter exceeds the maximal possible number of different configurations given the space used.

The additional counter will take the same amount of space as the computation already used plus the logarithm of the length of the input already scanned. Tracking of the amount of space used adds the logarithm of that used space to the total used space. So this approach to detect (avoid) repeated configurations works for any non-sublogarithmic space complexity class.


When I asked that question, I had in mind a technique for finding cycles which only works for deterministic machines: I take two copies of the machine, and always perform one step for the first machine and two steps for the second machine, and then compare the configurations of the two machines. Those configurations can only be equal if the machines cycles, and any cycle will be found before the first machine repeats a configuration.

This technique only works for deterministic machines, and only when copying the machine doesn't violate any resource restrictions. For example, it doesn't work for stack machines (because having two stacks is fundamentally different from having only one stack), and it doesn't work for machines which may only read their input once.


For machines which can read their input only in forward direction and only once, the above two techniques can be slightly modified. Each time a new symbol from the input is read, the entire machinery for detection of repeated configurations is reset, and starts again from zero. So the input position must no longer be included in the number of possible states, and the copied machines (of the second technique) no longer need any access to the input. This allows to apply those techniques also to DFAs.

Similar modifications to also make those techniques applicable to stack machines would be nice, because we know that PDAs have no problems with repeated configurations either.

$\endgroup$
  • $\begingroup$ Keeping a counter doesn't avoid cycling, it just ensures that cycles are detected and those runs are terminated early. This is a useful technical device when dealing with time-bounded classes, to make sure that a machine can't cycle beyond the polynomial time bound to reach an accepting state, but is not necessary for space-bounded classes. Further, adding a logarithmic counter to a TM means it always uses at least logarithmic space, even if the language it accepts is regular, so is usually avoided when studying classes below L. $\endgroup$ – András Salamon Feb 19 '16 at 16:03
  • $\begingroup$ @AndrásSalamon The machine which includes the counter and tracks the used space of the original machine is a different machine than the original machine. This machine still satisfies the resource restrictions, doesn't cycle (because the counter is part of the configuration), and still gives the same answer as the original machine. Cool, no? $\endgroup$ – Thomas Klimpel Feb 19 '16 at 16:46
  • $\begingroup$ "Logarithm of the length of the input already scanned" forces at least logarithmic space to be used, even when this isn't necessary, as for a DFA recognizing a regular language. The new machine only satisfies resource restrictions that allow at least logarithmic space. $\endgroup$ – András Salamon Feb 19 '16 at 17:21
  • $\begingroup$ @AndrásSalamon The interesting fact is that cycling can be avoided for DFA and NFA, only the two techniques described in this answer won't work for that case. (They won't work for PDAs either, which is more sad. But one can't have everything.) $\endgroup$ – Thomas Klimpel Feb 19 '16 at 19:29

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.