153
правки
Изменения
Нет описания правки
{{Определение
|definition=
'''Проблемой соответствий Поста(ПСП)''' (Post correspondence problem) называется проблема нахождения алгоритма, выясняющего для каждой постовской системы соответствия, существует ли решение этой системы.
}}
===Модифицированная проблема соответствий поста===
Рассмотрим промежуточную версию ПСП, которая называется '''модифицированной проблемой соответствий Поста''', или '''МПСП'''. В
модифицированной ПСП на решение накладывается дополнительное требование, чтобы первой парой в решении была пара первых элементов списков '''А''' и '''В'''. Более формально, экземпляр МПСП состоит из двух списков <tex>A = ( x_1 , \ldots , x_k )</tex> и <tex>B = ( y_k , \ldots , y_k )</tex>, и решением является последовательность из О или нескольких целых чисел <tex>i_1, \ldots, i_m</tex> при которой <tex>x_1 x_{i_1} \ldots x_{i_k} = y_1 y_{i_1} \ldots y_{i_m}</tex>
{{Теорема
|statement=
