2
$\begingroup$

I can't find space complexity of this problem with search engines.

I think I have NL algorithm for it (just a basic "one by one non-deterministically accept values if possible"), but I wonder what other research was done on it.

Any references and/or ideas?

Improve this question
$\endgroup$
3
  • $\begingroup$ Should that not be in plain $L$? The only extra space needed for one pass through the input word is for storing two counters (in binary, not exceeding the length of the input word), one for the currently largest length seen and one for the current length. $\endgroup$
    – Kai
    Commented Apr 8 at 9:15
  • $\begingroup$ @Kai subsequence here isn't in a row. Deciding which symbols to skip is the hard part $\endgroup$
    – Noone AtAll
    Commented Apr 11 at 1:39
  • $\begingroup$ Perhaps you could edit the question to add a proper definition of the problem. $\endgroup$
    – Kai
    Commented Apr 11 at 8:32

1 Answer 1

Reset to default
1
$\begingroup$

closest I could find so far:
https://arxiv.org/abs/2002.08498 provides an SC algoritgm (polylog space, poly time) for approximation of LIS

savitch seems to give smallest space so far

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.