Язык находится в если существует машина Тьюринга для пространства журналов, которая решает язык с полиномиальным количеством рекомендаций.
Смотрите здесь для получения дополнительной информации: https://en.wikipedia.org/wiki/L/poly
Вопрос
Каковы последствия ?
Ответы:
Одно простое следствие - . Доказательство. Для любого языка A ∈ P / poly существует язык B ∈ P и последовательность консультативных строк полиномиальной длины y 1 , y 2 , y 3 , … таких, что x ∈ AP/poly=L/poly A∈P/poly B∈P y1,y2,y3,… . По предположению, существует язык C ∈ L и последовательность консультативных строк полиномиальной длины z 1 , z 2 , z 3 , … такая, что ( x , y ) ∈ Bx∈A⟺(x,y|x|)∈B C∈L z1,z2,z3,… . Отсюда следует, что A ∈ L / poly ; строка рекомендации для x : ( y | x | , z | ( x , y | x | ) | ) .(x,y)∈B⟺(x,y,z|(x,y)|)∈C A∈L/poly x (y|x|,z|(x,y|x|)|)
(Краткий вариант доказательства:P⊆L/poly⟹P/poly⊆(L/poly)/poly=L/poly
источник