Вопрос: разрещимы ли диафантовы уранения для конечной группы

[erwins]

разрещимы ли диафантовы уранения для конечной группы, т.е. можно ли построить алгоритм скорость работы которого меньше чем время полного перебора.

[Xaositect]

erwins в сообщении #366429 писал(а):

разрещимы ли диафантовы уранения для конечной группы, т.е. можно ли построить алгоритм скорость работы которого меньше чем время полного перебора.

Что Вы называете диофантовым уравнением для конечной группы? Если это $x_1^{p_1}x_2^{p_2}\dots x_n^{p_n} = c$, то, очевидно, разрешимы. Но мне почему-то кажется, что Вы имеете в виду что-то другое, возможно, полиномы над $\mathbb{Z}/p\mathbb{Z}$.
Термин "разрешимость", кстати, означает существование алгоритма вообще, а не эффективного алгоритма.

[erwins]

Термин "разрешимость", кстати, означает существование алгоритма вообще, а не эффективного алгоритма. - вы не правы.
Для Диафантового уравнения в целых числах есть алгоритм найти все решения - подставить все значения.

Да, я имею ввиду полином.

[Xaositect]

erwins в сообщении #366435 писал(а):

Для Диафантового уравнения в целых числах есть алгоритм найти все решения - подставить все значения.

Решений может и не быть, а перебрать все целые числа нельзя - их бесконечно много. Если нам гарантируют, что решение есть, то да, задача разрешима. Но проблема в том, что узнать, есть решения или нет, с помощью алгоритма нельзя.

erwins в сообщении #366435 писал(а):

Да, я имею ввиду полином.

Полиномы над чем? Если над конечными полями, но смотрите алгоритм Кантора-Цассенхауза.

[erwins]

Решений может и не быть, а перебрать все целые числа нельзя - их бесконечно много. - Это и есть проверка эффективности. Решение за конечное количество шагов и есть разрешимость.

Кантора-Цассенхауза. Спасибо, посмотрю.

Просто интересно с точки зрения времени разрешимости программ на прологе и устранимости бесконечных рекурсий.

Как я понимаю над конечной группой любой взоимнорекурсивный набор функций разрешим или не разрешим за конечное количество шагов в силу ограниченности количества значений?

[Xaositect]

erwins в сообщении #366441 писал(а):

Решений может и не быть, а перебрать все целые числа нельзя - их бесконечно много. - Это и есть проверка эффективности. Решение за конечное количество шагов и есть разрешимость.

Если решение есть - оно найдется. Если его нет - алгоритм зациклится. Это называется частичная разрешимость.

erwins в сообщении #366441 писал(а):

над конечной группой

Да что Вы привязались к конечным группам. Полиномы над кольцами, а с группами - групповые алгебры. Может, Вам они нужны?
Сформулируйте модель, в общем.

erwins в сообщении #366441 писал(а):

Как я понимаю над конечной группой любой взоимнорекурсивный набор функций разрешим или не разрешим за конечное количество шагов в силу ограниченности количества значений?

Если я верно понял, то я не был бы так уверен. Значений-то конечное число, а термов - бесконечное. И там может зациклиться рекурсия.

[erwins]

Есть группа из n элеменетов. На которой определены p операций над 2мя аргументами результат которых попадает в кольцо.

Из данных операций сформулировано конечное описание взоимнорекурсивных функций. За какое минимальное время можно получить все допустимые решения.

[Xaositect]

erwins в сообщении #366447 писал(а):

Из данных операций сформулировано конечное описание взоимнорекурсивных функций. За какое минимальное время можно получить все допустимые решения.

В смысле, эти операции считаются известными? И из них мы строим новую систему функций с помощью рекурсии? Или мы сами эти операции с помощью рекурсии определяем?
А "решение" - это решение уравнения $f(x) = c$, где $f$ - это одна из рекурсивно определяемых функций?

[erwins]

да

[Xaositect]

Xaositect в сообщении #366453 писал(а):

В смысле, эти операции считаются известными? И из них мы строим новую систему функций с помощью рекурсии? Или мы сами эти операции с помощью рекурсии определяем?

А на этот вопрос?

И еще, схема рекурсии имеет вид $f(x,y,\dots) = $какой-то формуле, или что-нибудь типа $f(x,g(y)) = g(y, f(x))$ тоже допустимо?

[erwins]

откуда растут ноги.

F(y,x+y)=F(x,y)+F(y-x,x)

найти все решения в кольце целых чисел порядка p

-- Вт окт 26, 2010 18:08:25 --

И еще, схема рекурсии имеет вид $f(x,y,\dots) = $какой-то формуле, или что-нибудь типа $f(x,g(y)) = g(y, f(x))$ тоже допустимо?

да

[maxal]

Возьмите для примера одну из задач, на которых базируются криптографические протоколы (например, дискретное логарифтмирование в группе точек эллиптической кривой над конечным полем). Это, как правило, задачи для решения которых требуется как минимум субэкспоненциальные алгоритмы (хотя это обычно строго не докаказано):
http://en.wikipedia.org/wiki/Computatio ... assumption

[Xaositect]

erwins в сообщении #366457 писал(а):

откуда растут ноги.

F(y,x+y)=F(x,y)+F(y-x,x)

найти все решения в кольце целых чисел порядка p

Замечательно.
Во-первых, это функциональное уравнение, и решением здесь является функция. Так что $f(x,y,\dots) = c$ мы рассматривать не будем.
Во-вторых, здесь все линейно, что может значительно упростить дело.

В-третьих, на ваш исходный вопрос я могу ответить - если допустимы общие схемы рекурсии типа $f(\dots g(\dots),h()) = \dots$, то проблема неразрешима даже при $n = 1$ в том смысле, что нельзя определить, определена ли функция на единственном элементе, или нет, так как эквивалентна проблеме полу-Туэ, если я не ошибаюсь.

[Xaositect]

erwins в сообщении #366457 писал(а):

F(y,x+y)=F(x,y)+F(y-x,x)

Хорошая задачка, кстати.

[erwins]

x принадлежит к (0,1)
+ определим как исключающее или

F(y,x+y)=F(x,y)+F(y-x,x) ===

x=0 y=0
F(0,1)=F(0,0)+F(1,0)
x=0 y=1
F(1,0)=F(0,1)+F(0,0)
и т д

Возникает мысль, что если операция + обратима и полна.ю то любой набор рекурсивных функций составленых из нее или всюду верен или всюду не верен

-- Ср окт 27, 2010 10:54:21 --

Если определена одна операция двухсмежная, ассоциативная и комутативная, то решение можно свети к
a*x+b*y+c*z....=0 где a* последовательное выполнение операции сложение a раз где а - целое число