1
$\begingroup$

Where I can find reference and documents on the work made for proving whether DLBA are equal NLBA nr not? What is the underlying problem? Why it is still an open question in TCS?

$\endgroup$
3
$\begingroup$

The 1998 chapter about the second LBA Problem, from Schöning and Pruim Gems of TCS mentions the first LBA problem. The chapter does not say much more than the wikipedia article though, apart from mentioning the related Savitch's theorem, whose optimality is a notorious open question.

Perhaps by looking at papers quoting the Kuroda or Savitch paper you could get a picture of recent results in the field?

$\endgroup$

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.