Короче говоря, теоремы иерархии времени говорят о том, что машина Тьюринга может решить больше проблем, если у нее будет больше времени для вычислений. Подробно для детерминированных TM и функций, построенных по времени, с это и для недетерминированных функций TM и функций времени, f, g с f (n + 1) = o (g (n)) это NTIME (f (n)) \ subsetneq NTIME (g (n)). Есть много (старых и текущих) результатов, которые используют теоремы иерархии времени, чтобы доказать нижние границы. Вот мои вопросы:f ( n ) log f ( n ) = o ( g ( n ) ) D T I M E ( f ( n ) ) ⊊ D T I M E ( g ( n ) ) f , g f ( n +) 1 ) = o ( g ( n ) ) N
Что произойдет, если мы сможем доказать лучший результат для детерминированного или недетерминированного случая?
Если мы можем доказать, что существует разрыв между детерминированной иерархией времени и недетерминированной иерархией времени, означает ли это ?
Ответы:
О вашем втором вопросе. Нет, это не подразумевает . Теоремы об иерархии в основном полезны для определения количества отдельного ресурса, необходимого для ТМ, чтобы можно было решить дополнительные проблемы.п≠ Nп
Например, мы знаем, что . Пусть , , такое, что и .f ( n ) = n g ( n ) h ( n ) f ( n + 1 ) = o ( g ( n ) ) f ( n ) l o g ( f ( n ) ) = o (Д ТяMЕ( n ) ≠ NTяMЕ( н ) е( n ) = n г( н ) ч ( н ) е( n + 1 ) = o ( г( н ) ) е( П ) л о г( ф( n ) ) = o ( h ( n ) )
Из теорем иерархии следует, что и . При этих предположениях возможно .Д ТяMЕ( ф( n ) ) ⊊ D TяMЕ( г( н ) ) NTяMЕ( ф( n ) ) ⊊ NTяMЕ( ч ( н ) ) NTяMЕ( г( n ) ) ⊆ D TяMЕ( ч ( н ) )
Теоремы об иерархии могут быть использованы для определения отношений между ресурсами при условии равенства между ними. Например, предположим, что . Мы знаем, что для такого что , не может быть равен из-за теоремы иерархии NTIME.N T I M E ( g ( n ) ) g ( n ) 2 n + 1 = o ( g ( n ) ) S P A C E ( н )NTяMЕ( 2N) = SпA CЕ( н ) NTяMЕ( г( н ) ) г( н ) 2n + 1= о ( г( н ) ) SпA CЕ( н )
источник
Иерархия также относится к континууму во времени и пространстве (рассматривается отдельно), и представляется возможным, что континуум не более «гранулирован», чем подразумевается в теоремах, т.е. они могут быть наилучшей возможной «гранулярностью».
Ваш второй вопрос кажется неясным или, возможно, не очень четко определенным, если вы не можете лучше определить, что вы подразумеваете под «пробелом». все разрешимые проблемы разрешимы где-то в обеих иерархиях. сложность состоит в том, чтобы определить взаимосвязи. один из редких «пробелов» или разделений в современной теории действительно был доказан в детерминированное время по сравнению с недетерминированным временем, так что [1]. см. также [2] для аналогичного вопроса и "недавних" достиженийDTIME(n)≠NTIME(n)
[1] PPST1983 http://dl.acm.org/citation.cfm?id=1382850
[2] NTIME (n ^ k) ≠ DTIME (n ^ k)?
источник