Является ли решение систем уравнений по модулю

Меня интересует сложность решения линейных уравнений по модулю k для произвольного k (и с особым интересом к простым степеням), а именно:

Проблема. Для данной системы из линейных уравнений по неизвестным по модулю , существуют ли какие-либо решения?н $m$$n$$k$

В аннотации к своей статье Структура и важность классов logspace-MOD для классов Mod _k L , Бунтрок, Дамм, Хертрампф и Майнель утверждают, что они « демонстрируют свою значимость, доказывая, что все стандартные задачи линейной алгебры над конечными кольцами полны для этих классов$\mathbb Z/k\mathbb Z$ ". При ближайшем рассмотрении история сложнее. Например, Buntrock et al. показать (с помощью наброска доказательства в более раннем и свободно доступном проекте, найденном Каве, спасибо!), что решение систем линейных уравнений вместо этого находится в дополнительном классе coMod _k L , для kпремьер. Этот класс, как известно, не равен Mod _k L для k составного, но не говоря уже о том, что - меня беспокоит тот факт, что они не делают никаких замечаний относительно того, содержится ли решение систем линейных уравнений mod k даже в комоде _k L для k композита!

Вопрос: содержится ли решение систем линейных уравнений по модулю k в coMod _k L для всех положительных k?

Если вы можете решать системы уравнений по модулю более высокой степени q простого числа p , вы также можете решать их по модулю p ; Таким образом, решение систем уравнений по модулю q является условным _р L- трудным. Если бы вы могли показать, что эта проблема в Mod _q L , вы бы в конечном итоге показали Mod _k L  =  coMod _k L для всех k . Это, вероятно, будет трудно доказать. Но это в комоде _K L ?

Я счастлив сказать, что думаю, что мы можем ответить на этот вопрос утвердительно: то есть, решить, возможна ли линейная конгруэнция, по модулю k, является kMod _k L -полным.

Мы можем фактически свести эту проблему к частному случаю простых степеней. Можно показать, что:

Нормальная форма. Класс coMod _k L состоит из языков L вида L  =  L _{p 1}  ∩  L _{p 2}  ∩ ... ∩  L _{p r}  , где L _{p j}  ∈  coMod _{p j}  L и где p _j лежит над простыми множителями k ,

По теореме остатка любое решение системы уравнений по модулю каждой из простых степеней делящей k, приводит к решению той же системы mod k . Таким образом , если решение систем линейных уравнений над содержится в Comod _{р J}  L , то отсюда следует , что решение систем уравнений мод к содержится в Comod _K L . P T J$p_{\!j}^{e_j}$$p_{\!j}^{t_j}$

Существует стандартный алгоритм, описанный McKenzie и Cook для уменьшения линейных конгруэнций по модулю простой степени для построения остовного множества для его нулевого пространства (а именно, для A x  =  y над данным кольцом, построить базис для нулевого пространства в [  A  |  y  ] и посмотреть, существуют ли какие-либо решения с конечным коэффициентом -1); и впоследствии для сведения построения пространств нулей по модулю простых степеней к построению пространств нулей по модулю простых чисел и умножению матриц по простым степеням. Обе последние задачи являются задачами, которые выполнимы для coMod _k L , при условии, что вы можете построить соответствующие матрицы.

Оказывается, что матрицы, участвующие в редукции Маккензи и Кука, сами могут быть вычислены путем умножения матриц и (что крайне важно) деления на постоянный множитель. К счастью, для простых степеней коэффициенты задействованных матриц могут быть вычислены на рабочей ленте с помощью оракула для машин coMod _p L ; и деление на константу может быть выполнена в NC ¹ , что опять - таки возможно в Comod _р L . Так получается, что вся проблема в конечном счете выполнима в Comod _K L .

Для получения полной информации см. [ Arxiv: 1202.3949 ].