2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

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

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

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

 
 
 
 Re: Вопрос: разрещимы ли диафантовы уранения для конечной группы
Сообщение26.10.2010, 16:20 
Аватара пользователя
erwins в сообщении #366435 писал(а):
Для Диафантового уравнения в целых числах есть алгоритм найти все решения - подставить все значения.
Решений может и не быть, а перебрать все целые числа нельзя - их бесконечно много. Если нам гарантируют, что решение есть, то да, задача разрешима. Но проблема в том, что узнать, есть решения или нет, с помощью алгоритма нельзя.

erwins в сообщении #366435 писал(а):
Да, я имею ввиду полином.
Полиномы над чем? Если над конечными полями, но смотрите алгоритм Кантора-Цассенхауза.

 
 
 
 Re: Вопрос: разрещимы ли диафантовы уранения для конечной группы
Сообщение26.10.2010, 16:25 
Решений может и не быть, а перебрать все целые числа нельзя - их бесконечно много. - Это и есть проверка эффективности. Решение за конечное количество шагов и есть разрешимость.

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

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

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

 
 
 
 Re: Вопрос: разрещимы ли диафантовы уранения для конечной группы
Сообщение26.10.2010, 16:33 
Аватара пользователя
erwins в сообщении #366441 писал(а):
Решений может и не быть, а перебрать все целые числа нельзя - их бесконечно много. - Это и есть проверка эффективности. Решение за конечное количество шагов и есть разрешимость.
Если решение есть - оно найдется. Если его нет - алгоритм зациклится. Это называется частичная разрешимость.

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

erwins в сообщении #366441 писал(а):
Как я понимаю над конечной группой любой взоимнорекурсивный набор функций разрешим или не разрешим за конечное количество шагов в силу ограниченности количества значений?
Если я верно понял, то я не был бы так уверен. Значений-то конечное число, а термов - бесконечное. И там может зациклиться рекурсия.

 
 
 
 Re: Вопрос: разрещимы ли диафантовы уранения для конечной группы
Сообщение26.10.2010, 16:43 
Есть группа из n элеменетов. На которой определены p операций над 2мя аргументами результат которых попадает в кольцо.

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

 
 
 
 Re: Вопрос: разрещимы ли диафантовы уранения для конечной группы
Сообщение26.10.2010, 16:54 
Аватара пользователя
erwins в сообщении #366447 писал(а):
Из данных операций сформулировано конечное описание взоимнорекурсивных функций. За какое минимальное время можно получить все допустимые решения.

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

 
 
 
 Re: Вопрос: разрещимы ли диафантовы уранения для конечной группы
Сообщение26.10.2010, 16:57 
да

 
 
 
 Re: Вопрос: разрещимы ли диафантовы уранения для конечной группы
Сообщение26.10.2010, 17:01 
Аватара пользователя
Xaositect в сообщении #366453 писал(а):
В смысле, эти операции считаются известными? И из них мы строим новую систему функций с помощью рекурсии? Или мы сами эти операции с помощью рекурсии определяем?

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

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

 
 
 
 Re: Вопрос: разрещимы ли диафантовы уранения для конечной группы
Сообщение26.10.2010, 17:07 
откуда растут ноги.

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))$ тоже допустимо?

да

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

 
 
 
 Re: Вопрос: разрещимы ли диафантовы уранения для конечной группы
Сообщение26.10.2010, 17:29 
Аватара пользователя
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$ в том смысле, что нельзя определить, определена ли функция на единственном элементе, или нет, так как эквивалентна проблеме полу-Туэ, если я не ошибаюсь.

 
 
 
 Re: Вопрос: разрещимы ли диафантовы уранения для конечной группы
Сообщение26.10.2010, 20:02 
Аватара пользователя
erwins в сообщении #366457 писал(а):
F(y,x+y)=F(x,y)+F(y-x,x)
Хорошая задачка, кстати.

 
 
 
 Re: Вопрос: разрещимы ли диафантовы уранения для конечной группы
Сообщение27.10.2010, 09:18 
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 раз где а - целое число

 
 
 [ Сообщений: 15 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group