1

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?

asdf
  • 153
  • 5

1 Answers1

3

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?

Community
  • 1
Joseph Stack
  • 1,095
  • 6
  • 13