Проблеми ExpSpace, з якими проблеми доступу до конфігурації знаходяться в P/poly?

Чи є відомі про проблеми ExpSpace, з якими проблеми доступу до конфігурації знаходяться в P/poly?

Нехай $ M $ - машина ExpSpace.   Враховуючи дві конфігурації $ a $ і $ b $ $ M $ (максимальної довжини) та ціле число $ t $,   може $ M $ досягати $ b $ з $ a $ в $ t $ кроках?

Зверніть увагу, що довжина $ a $, $ b $ і $ t $ експоненціально велика в термінах вхідного значення в $ M $.

Таким чином, машина P/poly виконує експоненціальний час з експоненціально довгою довідковою ланкою. Але з очевидних причин це не повинно бути чимось на зразок $ \ mathsf (EXPSPACE) \ cap \ mathsf (EXP/exp) $ (і, отже, просто EXPSPACE).

0
Я відредагував питання для чіткості, але я думаю, що досі незрозуміло, що ви точно шукаєте. Що ти дійсно потребуєш?
додано Автор Swinders, джерело
@Kaveh Я просто хотів дізнатися, наскільки потужним він є. Але тепер я знайшов, що він просто міститься в $ \ Sigma ^ 2 \ mathrm (EXP) $. Питання стає таким: чи він дорівнює $ \ Sigma ^ 2 \ mathrm (EXP) $? Але це не повинно бути таким цікавим зараз. І вибач за мою англійську в будь-якому випадку.
додано Автор Kyle Li, джерело

Відповідей немає

0