Чи існує додаткова теорема про часові ієрархії?

Я хотів би щось подібне до цього:

Сутність: існує функція $ g (n) $ така, що для всіх функцій $ f (n) $ (можливо, задовольняють деякі розумні властивості, такі як конструктивність часу) існує мова в $ TIME [f (n )] $, що не в $ TIME [f (n) - g (n)] $.

Чи щось подібне до цього відомо? Чи можна це довести за будь-яким розумним припущенням? Чи буде це мати які-небудь цікаві наслідки?

By $TIME[f(n)]$, I mean the set of problems solved by a Turing machine that halts in exactly $f(n)$ steps or less - not to be confused with $O(f(n))$ or less, in which case the conjecture is trivially false when $f(n) >> g(n)$.

2
Розбиття відбуваються за допомогою діагоналізації і вимагають моделювання меншого класу, а симуляція вимагає асимптотичного домінування меншої функції. Крім того, я думаю, що те, що ви хочете, суперечить швидким теоремам.
додано Автор Swinders, джерело

1 Відповіді

Я не бачу потреби у вашому роз'ясненні, оскільки через лінійне прискорення ці набори точно такі ж. Зрозуміло, чому вам слід уникати використання асимптотико, оскільки $ f (n) -g (n) $ та $ f (n) $ асимптотично однакові, але не використовуючи асимптотику, якось не роблять теорему лінійної прискорення неправда.

Можна отримати додаткову інформацію. $ g (n) $ - це фактично $ g (f (n)) $, тобто. він повинен залежати від $ f (n) $ для роботи з усіма функціями. Чому? Припустимо, що g (n) не постійне. Виберіть $ f (n) = 2 g (n) $. Тоді ясно, що $ f (n) $ та $ f (n) -g (n) $ рівні за теоремою лінійної прискорення. Якщо $ g (n) = c $ є постійним, то ми можемо вибрати непостійний $ f (n) $ так, щоб гіпотеза не мала.

Що робити, якщо ми дозволяємо залежність від $ f (n) $? Тоді, беручи відому теорему про детерміністичну ієрархію та виконуючи деяку базову арифметику, ми можемо побачити, що будь-який $ g (f (n)) $, який є $ o ((1 - \ frac {1} {\ log f (n)}) f (n)) $ працює. Однак я не впевнений, що просто затвердження однієї і тієї ж теореми в дещо іншому вигляді відкриває можливість нового розуміння.

3
додано
Теорема про прискорення - це те, що я мав би побачити, але це не відповідає духу питання. Можливо, я повинен був сказати, що ТМ повинні мати алфавіт $ \ (0, 1, B \) $, щоб заборонити такий трюк.
додано Автор SteveDonie, джерело
Як це суперечить теоремі прискорення? Теорема прискорення не говорить про те, що всі функції можуть бути підсиленими, тільки що існують деякі, які не можуть. Чому не може бути одна функція, яку неможливо розігнати, а інша - здатна?
додано Автор hysteryteacher, джерело