Лог-ғарыштық түрлендіргіш - Log-space transducer

A журналы түрлендіргіш (LST) түрі болып табылады Тьюринг машинасы үшін қолданылған кеңістікті қысқарту.

Журналдық түрлендіргіш, ${displaystyle M}$ , үш таспа бар:

Тек оқу үшін енгізу таспа.
Оқу / жазу жұмыс таспа (ең көп дегенде шектелген ${displaystyle O (log n)}$ таңбалар).
Тек жазу, бір рет жазу шығу таспа.

${displaystyle M}$ есептеуге арналған болады лог-кеңістікті есептеу функциясы ${displaystyle fcolon Sigma ^ {ast} ightarrow Sigma ^ {ast}}$ (қайда ${displaystyle Sigma}$ болып табылады алфавит екеуінің де енгізу және шығу таспалар). Егер ${displaystyle M}$ бірге орындалады ${displaystyle w}$ оның енгізу таспа, машина тоқтаған кезде ол болады ${displaystyle f (w)}$ қалған шығу таспа.

Тіл ${displaystyle Asubseteq Sigma ^ {ast}}$ деп айтылады қысқартылатын кеңістік тілге ${displaystyle Bsubseteq Sigma ^ {ast}}$ егер бар болса а лог-кеңістікті есептеу функциясы, ${displaystyle f}$ , бұл кірісті проблемадан түрлендіреді ${displaystyle A}$ мәселені енгізу үшін ${displaystyle B}$ . И.Е. ${displaystyle win Aiff f (w) in B}$ .

Бұл өте қысылған идея сияқты көрінеді, бірақ оның екі пайдалы қасиеті бар, оларды азайту қажет:

Транзитивтілік қасиеті бар. (A B-ға, B B-ге C-ге, A-ға C-ге дейін азайтады).
Егер А В-ға дейін азайтылса, ал В мәнінде L, содан кейін біз A-ді білеміз L.

Транзитивтілік бір редуктордың шығыс лентасын (А → В) екіншісіне (В → С) беруге болатындықтан өтеді. Бір қарағанда, бұл дұрыс емес сияқты, өйткені A → C редукторы B → C редукторына беру үшін A → B редукторынан шығыс таспаны жұмыс таспасына сақтау керек, бірақ бұл дұрыс емес. B → C редукторы кіріс таспасына кіру керек болған сайын, A → C редукторы A → B редукторын қайта іске қосуы мүмкін, сондықтан A → B редукторының шығысы ешқашан бір уақытта толығымен сақталуы керек емес.

Әдебиеттер тізімі

Сепиетовский, Анджей (1994), Сублогарифмдік кеңістіктегі тюринг машиналары , Springer Press, ISBN 3-540-58355-6. 2008-12-03 шығарылды.
Sipser, Майкл (2012), Есептеу теориясына кіріспе, Cengage Learning, ISBN 978-0-619-21764-8.

P ≟ NP

Бұл теориялық информатика - қатысты мақала а бұта. Сіз Уикипедияға көмектесе аласыз оны кеңейту.