Каковы последствия

14

Язык находится в если существует машина Тьюринга для пространства журналов, которая решает язык с полиномиальным количеством рекомендаций.L/поLY

Смотрите здесь для получения дополнительной информации: https://en.wikipedia.org/wiki/L/poly

Вопрос

Каковы последствия ?пL/поLY

Майкл Вехар
источник
Примечание: L / poly также характеризуется как класс языков, имеющих программы разветвления полиномиального размера.
Майкл Вехар
1
Известны ли какие-нибудь интересные последствия L = P? (Интересно, что (а) требуется нетривиальное доказательство и (б) следствием является не просто то, что P будет иметь такое-то свойство, которым L безусловно обладает)
Уильям Хоза
В моем вопросе я открыт для любых последствий, которые пользователи считают значимыми для них, даже если они тривиальны. Несколько потенциальных последствий , которые я задавался вопросом о том, были ли означает , может быть , P = L или P / р о л у = L / р O л у или что - то еще более слабое отношение к этому. :)пL/поLYпзнак равноLп/поLYзнак равноL/поLY
Майкл Вехар
1
Справедливо! действительно является следствием; см мой ответ для доказательства. п/поLYзнак равноL/поLY
Уильям Хоза
1
@WilliamHoza Кроме того, я думаю, что подразумевает D T I M E ( t ( n ) ) N T I M E ( t ( n ) ) для определенных функций t ( n ) . См. «О разделителях, разделителях и времени и пространстве» для получения дополнительной информации. пзнак равноLDTяMЕ(T(N))NTяMЕ(T(N))T(N)
Майкл Вехар

Ответы:

9

Одно простое следствие - . Доказательство. Для любого языка A P / poly существует язык B P и последовательность консультативных строк полиномиальной длины y 1 , y 2 , y 3 , таких, что x AP/poly=L/polyAP/polyBPy1,y2,y3, . По предположению, существует язык C L и последовательность консультативных строк полиномиальной длины z 1 , z 2 , z 3 , такая, что ( x , y ) BxA(x,y|x|)BCLz1,z2,z3, . Отсюда следует, что A L / poly ; строка рекомендации для x : ( y | x | , z | ( x , y | x | ) | ) .(x,y)B(x,y,z|(x,y)|)CAL/polyx(y|x|,z|(x,y|x|)|)

(Краткий вариант доказательства: PL/polyP/poly(L/poly)/poly=L/poly

Уильям Хоза
источник
Потрясающие! Большое спасибо. Я очень ценю это. :)
Майкл Вехар