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

19

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

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

В аннотации к своей статье Структура и важность классов logspace-MOD для классов Mod k L , Бунтрок, Дамм, Хертрампф и Майнель утверждают, что они « демонстрируют свою значимость, доказывая, что все стандартные задачи линейной алгебры над конечными кольцами полны для этих классовZ/kZ ". При ближайшем рассмотрении история сложнее. Например, 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 ?

Ниль де Бодрап
источник
ссылка citeseerx на черновик статьи . ps: более надежный способ работы с modk использует modkA где A[k1] - это набор принятых напоминаний modk . Есть также связанный вопрос в сложности доказательства, ср. « Доказательство сложности линейной алгебры » Солтиса и Кука, APAL 2004.
Kaveh
2
а как насчет просто k = 4 и четности-L?
Домоторп

Ответы:

9

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

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

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

По теореме остатка любое решение системы уравнений по модулю каждой из простых степеней делящей k, приводит к решению той же системы mod k . Таким образом , если решение систем линейных уравнений над содержится в Comod р L , то отсюда следует , что решение систем уравнений мод к содержится в Comod K L . P T Jpjejpjtj

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

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

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

Ниль де Бодрап
источник
Я хотел бы знать, является ли постоянным в вашем вопросе / ответе? Меня интересует случай, когда размер не является неограниченным. кkk
Хуан Бермехо Вега
1
@Juan: Да, является константой, хотя и любой константой. k
Ниль де Бодрап,