Целые точки на кривых второго порядка.

[maxal]

pronix в сообщении #355209 писал(а):

Если знаете такой метод, то примените его к уравнению (т.е. покажите, имеет оно целые корни или нет) $6x^2+6xy+12x+7y-31272=0$.

Это уравнение равносильно

$$(6x + 7)(6x + 6y + 5) = 187667$$

Ну дальше раскладывайте $187667$ на пару сомножителей всеми возможными способами и решаете систему линейных уравнений относительно $x,y$.

[pronix]

Цитата:

Это уравнение равносильно
$(6x+7)(6x+6y+5)=187667$
Ну дальше раскладывайте $187667$ на пару сомножителей всеми возможными способами и решаете систему линейных уравнений относительно $x,y$.

maxal, это мне понятно . Только вы меня, наверное, неправильно поняли. Разложение на простые множители связано с сложностью факторизации больших чисел, что вы мне и советуете. А если увеличить свободный член порядков эдак на 15. Что дальше? Тоже разлаживать? Ales же утверждает, что для определения хотя бы одного решения, факторизация не нужна. Меня интересует, каким способом, не связанным с факторизацией больших чисел, можно найти хотя бы одно решение данного уравнения.

[maxal]

pronix в сообщении #355226 писал(а):

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

Возможно он говорил конкретно о $x^2-y^2=N$, у которого для нечетного $N$ всегда есть решение $x=\frac{N+1}{2}$ и $y=\frac{N-1}{2}$.

[Алексей К.]

Я, как не специалист в целочисленных задачах, более не встревал. Но нижепроцитированное мне показалось противоречивым.

pronix в сообщении #354286 писал(а):

Метод решения, конечно, красивый, но далеко не универсальный, так как там всё сводится к разложению на простые множители свободного члена $f$, что неэффективно и трудоёмко при достаточно больших $f$.

Ales в сообщении #355140 писал(а):

Если надо найти хотя бы одно решение, а не все, факторизация в данном примере не нужна. Поэтому это не совсем тривиальный вопрос.

Поверим автору, что всё сложно при больших $f$. Сделаем из этого вывод, что всё тривиально при $f=0$. Здесь, видимо, необходим смайлик. Поставим какой-нть:
Поверим, что Ales без факторизации найдёт автору хотя бы одно решение ($x_0,y_0$). Тогда, соответствующим переносом ($x\to x+x_0,\;\ldots$), автор приведёт свою формочку к формочке с $f=0$. Целочисленность не пострадает (перенос целочисленный), а задача станет "тривиальной" ($f=0$). Кто неправ?

По (непроверенным) ощущениям, неправ автор, сопоставив трудоёмкость с величиной $f$. Здесь, скорее, работает какой-то инвариант, $I(a,b,c,d,f)$, относительно переносов.

-- 22 сен 2010, 23:01 --

О, возникло ощущение, что неправ я!

[Ales]

pronix в сообщении #355209 писал(а):

maxal, спасибо за развёрнутый ответ.

Цитата:

Если надо найти хотя бы одно решение, а не все, факторизация в данном примере не нужна. Поэтому это не совсем тривиальный вопрос.

А вот это уже интересно (для меня по крайней мере)! Ales, можете пояснить? Т.е. получается, что существует метод, который не зависит от сложности факторизации больших чисел? Как я уже писал выше, сейчас решаю одну задачу и дошёл до этапа, когда нужно найти корни уравнения второй степени от двух неизвестных в целых числах. Общего случая нет, но мне очень облегчит дальнейшее продвижении в решении задачи хотя бы знание того, что у уравнения есть хотя бы одна пара целых кореней ($x;y$). Если знаете такой метод, то примените его к уравнению (т.е. покажите, имеет оно целые корни или нет)
$6x^2+6xy+12x+7y-31272=0$. Буду очень признателен.

Да ничего интересного, увы, наоборот: тривиальное и очевидное.
Просто уравнение$ xy=N$, имеет решения в целых, без всякой факторизации.
Бывает часто, что надо знать хотя бы одно решение, а не все.
Поэтому факторизация не всегда обязательна.

Если Вам надо найти хотя-бы одно решение, то контрдовод насчет факторизации в том виде, как он был приведен, не годится.

-- Ср сен 22, 2010 22:22:37 --

maxal в сообщении #355237 писал(а):

pronix в сообщении #355226 писал(а):

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

Возможно он говорил конкретно о $x^2-y^2=N$, у которого для нечетного $N$ всегда есть решение $x=\frac{N+1}{2}$ и $y=\frac{N-1}{2}$.

Да, конечно, это я и имел в виду.
Просто интересная проблема (P - NP) требует найти хотя бы одно решение. Меня эти уравнения интересуют именно с этой стороны.

-- Ср сен 22, 2010 22:37:27 --

Вопрос о сложности решения уравнений второго порядка от двух переменных - открытая проблема.

Решение уравнения второго порядка от многих переменных - NP-полная задача.

-- Ср сен 22, 2010 22:45:00 --

pronix в сообщении #355209 писал(а):

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

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

[maxal]

Ales в сообщении #355270 писал(а):

Бывает часто, что надо знать хотя бы одно решение, а не все.
Поэтому факторизация не всегда обязательна.

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

$$(4x+3)(4y+3)=N$$

для $N$ являющего произведением двух простых вида $4k+3$ с необходимостью даёт факторизацию $N$.

[Ales]

maxal в сообщении #355286 писал(а):

Ales в сообщении #355270 писал(а):

Бывает часто, что надо знать хотя бы одно решение, а не все.
Поэтому факторизация не всегда обязательна.

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

$$(4x+3)(4y+3)=N$$

для $N$ являющего произведением двух простых вида $4k+3$ с необходимостью даёт факторизацию $N$.

ОК.
Вы правы, что сразу натыкаешься на факторизацию.
Но не очевидно, что она логически вытекает и всегда равна по сложности.
Неудачный пример: $-\frac{N+3} 4; -1$.

-- Чт сен 23, 2010 00:13:46 --

Любая математическая проблема сводится к задаче поиска натуральных точек на параболе.

Например: существует ли доказательство гипотезы Римана (или теоремы Ферма) состоящее не более чем из триллиона знаков определенного алфавита? Кропотливая, муторная и не интересная работа позволит свести этот вопрос к решению уравнений вида $ax^2+by=c$ в натуральных числах.
Но такие уравнения решаются пока только перебором.
Выходит, что математика - это всего лишь перебор разных вариантов, или не так?

[maxal]

Ales в сообщении #355297 писал(а):

Любая математическая проблема сводится к задаче поиска натуральных точек на параболе.

Не говорите ерунды.
Сведите хотя бы доказательство гипотезы Пуанкаре к поиску "натуральных точек на параболе" - тогда и поговорим.

[Ales]

maxal в сообщении #355314 писал(а):

Ales в сообщении #355297 писал(а):

Любая математическая проблема сводится к задаче поиска натуральных точек на параболе.

Не говорите ерунды.
Сведите хотя бы доказательство гипотезы Пуанкаре к поиску "натуральных точек на параболе" - тогда и поговорим.

Доказательство можно формализовать.
Значит есть алгоритм, позволяющий быстро проверить, является ли некий текст доказательством гипотезы Пуанкаре.
Решение NP-полной задачи позволит по этому алгоритму найти подходящий текст.
Или не так?
Свести решение к уравнению второго порядка возможно и способ описан.

[maxal]

Ales
Теперь понятно, о чём вы. Вот соответствующая цитата из википедийной статьи Automated theorem proving:
For the frequent case of propositional logic, the problem is decidable but Co-NP-complete, and hence only exponential-time algorithms are believed to exist for general proof tasks.

Однако, утверждать, что "любая математическая проблема сводится к задаче поиска натуральных точек на параболе", всё равно нельзя. В частности, проблемы не лежащие в NP к ней не сводятся. Примером такой задачи является, например, поиск лучшего хода в шахматах или го - эта задача EXPTIME-полна, а потому не лежит ни в P, ни в NP.

[Ales]

maxal в сообщении #355334 писал(а):

Ales
Теперь понятно, о чём вы. Вот соответствующая цитата из википедийной статьи Automated theorem proving:
For the frequent case of propositional logic, the problem is decidable but Co-NP-complete, and hence only exponential-time algorithms are believed to exist for general proof tasks.

Однако, утверждать, что "любая математическая проблема сводится к задаче поиска натуральных точек на параболе", всё равно нельзя. В частности, проблемы не лежащие в NP к ней не сводятся. Примером такой задачи является, например, поиск лучшего хода в шахматах или го - эта задача EXPTIME-полна, а потому не лежит ни в P, ни в NP.

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

-- Чт сен 23, 2010 10:03:02 --

Все математические доказательства сводятся.
Если решить Co-NP полную задачу (поиск натуральных точек на параболе), то математикам останется только придумывать вопросы и создавать новые формальные модели, а решения, ответы, доказательства будет давать компьютер.

[pronix]

Цитата:

Да ничего интересного, увы, наоборот: тривиальное и очевидное.
Просто уравнение $xy=N$, имеет решения в целых, без всякой факторизации.
Бывает часто, что надо знать хотя бы одно решение, а не все.
Поэтому факторизация не всегда обязательна.

Если Вам надо найти хотя-бы одно решение, то контрдовод насчет факторизации в том виде, как он был приведен, не годится.

Теперь понятно, что вы имели в виду.

Цитата:

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

Если задача не решается с одной стороны, нужно подойти с другой. Во всяком случае даже отрицательный результат тоже результат. А в оракулов я не верю .

Цитата:

Сведите хотя бы доказательство гипотезы Пуанкаре к поиску "натуральных точек на параболе" - тогда и поговорим.

Хотел бы я увидеть лицо Перельмана .

[Ales]

Алгоритм, позволяющий найти хотя бы одно решение уравнения $x^2=a+Ny$, приводит к факторизации числа $N$.
Для заданного N решим уравнение $x^2=b^2+Ny$, тогда с вероятностью $\frac 1 2$ (если N - произведение двух простых и даже больше, если N - более сложное произведение) НОД$(x-b,N)$ будет нужным делителем N. Повторяя пробы для разных $b$, очень скоро найдем делитель N.

Так что, даже требование найти хотя бы одно решение такого простого уравнения, как $x^2=a+Ny$ равно по сложности факторизации.

А если бы в уравнении было много (сколько угодно) переменных, то это была бы вообще NP-полная задача.