Join Yalantis and get a $1000 sign-in bonus! React.js, React Native, Python, Java, DevOps, BА. Apply now!
×Закрыть

P=NP-Complete тестируем!

Вот и настал тот день!)))
Мне удалось решить NP-полную задачу, за полиномиальное время(O(N^4) или быстрее), задача Точное покрытие (Excat Cover). Сделал сайтик, на котором можно протестировать. Генератор с его исходником прилагается. На выходе получаем текстовый файл, который в конце содержит решение, для того что бы проверить правильность работы, кто будет постить тесты, удаляйте пожалуйста все что после строки с маркером «m», включая саму строку. Приветствуется критика, и замечания по самому сайту. Если у меня нет алгоритма и программы то даже на самое не большое количество строк скажем 60, уйдет очень очень большое время [math]2^60[/math] операций выбора и сравнения, даже если каждая операция будет занимать 1 такт процессора, даже при 100 мрлд операций в секунду, на нахождение решения потратится 11 млн сек.

npcomplete-001-site1.myasp.net

👍НравитсяПонравилось0
В избранноеВ избранном0
LinkedIn
Допустимые теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter
Допустимые теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter

Во-первых, TC либо толстый тролль, либо неумелый шарлатан. Чтобы убедится в этом — достаточно взглянуть на код генератора тестовых данных. В файле RandomGen.cs, в ворохе криптокода, есть интересная логика генерации так называемого «HiddenSolution»
Console.WriteLine("Save data to file...", Environment.NewLine); SaveToFile(SourceData, file); Console.WriteLine("{0}Stage 5 Done", Environment.NewLine); if (WeatherSaveHiddenSolution) { Console.WriteLine("Save hidden solution data to file...", Environment.NewLine); SaveHiddenSolutionToEnd(HiddenSolution,file); }

Очевидно, что при генерации, создать список множест, покрывающих заданое {1..N} не составляет труда.

Во-вторых, если бы даже ТС решил эту задачу за полиномиальное время, это доказывает равенство классов P=NP, а всего лишь показывает, что все задачи которые сводятся к данной за полиномиальное время детерминированным алгоритмом принадлежат к классу P.

В-третьих,
indexSave = 0; goto LabelFindSubSet;
просто оставлю без комментария :)

P.S. готов извиниться за п. 1, если не прав

Дело в том что данные генерируются случайным образом, как видно из кода. Так как нельзя гарантировать, что в случайных данных будет возможно найти строки которые покрывают множество, то отдельно создаются множества которые его покрывают и случайным образом эти множества расставляются в списке. После чего в конец файла для того кто будет тестировать был ответ, вернее легче было проверить. Как рекомендуется его надо удалять перед отсылкой. Можно и не добавлять в результирующий файл за что отвечает соответствующая опция генератора. По такому принципу строятся пожалуй все генераторы подобных бэнчмарков/тестов. Отдельно замечу так как HiddenSolution распределяется по вписку случайно и не какой информации о том где они находятся нет, то найти его можно только имея алгоритм.

Что касается второго замечания, то речь идет о решение NP-полной задачи, класс NP шире и включает NP-трудные задачи. А NP-полные сводятся друг к другу за полиномиальное время.

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

1.

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

2. Из сайта:

I can’t open source because cryptographi possible down
Я думаю Вам должно быть известно, что задача Факторизации целых чисел (Integer factorization) не является NP-полной (по крайней мере это сейчас не доказано) и относится к классу NP-intermediate (en.wikipedia.org/...P-intermediate. RSA и многие другие распостраненные алгоритмы именно на этом и держатся. По-этому Ваши опасения по поводу влияния вашего кода на криптографию как минимум преждевременные.

3.

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

P.S. Все-таки хотел бы извиниться за резкий тон первого сообщения, Вы молодец, что вообще занимаетесь этой задачей и я желаю успехов в этом нелегком деле :). Буду с интересом следить за развитием событий.

Это очень сильные предположения о входных данных.
 ни каких предположений не делается, по крайне мере отношение к генератору моему, мне ведь присылают самые разные файлы, вот к примеру некто exc (не с этого форума) прислал совершенно уникальные бэнчмарки, правильные))))
Я думаю Вам должно быть известно, что задача Факторизации целых чисел (Integer factorization) не является NP-полной (по крайней мере это сейчас не доказано) и относится к классу NP-intermediate
но задача факторизации сводится к SAT, а это NP-полная задача.
Извините, но я не представляю КАК можно было написать такой код независимо от целей. И если код решения написан в таком же стиле, то оценить корректность и сложность алгоритма будет сложновато, даже имея исходники.
может где то я не прав, но программа это всегда черный ящик для заказчика, вот ты ведь не знаешь как MS Word внутри сделал, и ничего пользуешься, условно, Open Office терпеть ненавидишь, хотя у него открытый исходник и код типа «правильный». У меня два условия главных выполняются, время расчета и память. Ниже в этой теме reality_hacker сделал очень красивый код, вот только не задача, он память жрет и работает медленнее чем у меня, имею ввиду на больших задачах. Нет ведь разницы 1 сек или 5 сек, но зато есть разница 5 часов или 10 часов. И память у меня 22,8МB, у него 1,2GB и я так и не дождался окончания работы. Код не важен важен результат!
но задача факторизации сводится к SAT, а это NP-полная задача.
Если бы она сводилась к NP-полной за полиномиальное время, то очевидно, принадлежала бы к классу NP-полных задач. Cудя по-всему это не так, и ее относят к класуу NPI (то есть тех которые NP, но не P и не NPC, то есть NP = P U NPC U NPI)
cstheory.stackexchange.com/...and-npc/237#237
Выделю главное

Here’s a collection of some of the responses of problems between P and NPC:
Factoring

Пруфлинк, и я поверю, что это не так.

Опять же, если ты решил NPC задачу за полиномиальное время ( а автоматически все остальные NPC), но это не значит что ты решил все NP задачи, как раз по причине существования класса NPI. А пока совсем не доказано, что множество NPI задач — пустое, нельзая говорить, что с P=NPC => P=NP . И насколько я понимаю, научный мир еще далек от этого.

По-этому за криптографию пока можешь быть спокоен ;)

Код не важен важен результат!
Так а что является результатом в твоем случае? Письмо с решением и sure, you can trust me?
Лень ставить wine или mono в таком случае побеждает интерес потестить.
Кстати, Open- а точнее LibreOffice меня вполне устраивает, когда работает с родным форматом.

O(1) по памяти для такой задачи конечно круто, но боюсь тут не оценят. Ты бы на www.reddit.com/r/algorithms запостил, там больше полезного фидбека будет. А сюда можешь писать веселые истории про ХРов и апдейты курса доллара.

На самом деле ДОУ больше по части инфраструктуры и жизни программистов чем о программировании самом.

Я написал на многие форумы, но как не странно подавляющие большинство тестов пришло именно от сюда. Тенденция такая что люди не понимаю с чем имеют дело. Спасибо за ссылку, попробую.

Какой максимальный набор входных множеств вы тестили? Что означает точность O(N^4)? Я так понимаю под N понимается количество входных множеств, как будет расти время выполнения в зависимости от размера входного множества(тоесть задачи где десяток множеств, но в них по миллиарду елементов)? Как ваши результаты соотносятся с результатами из статьи www.csc.kth.se/...over-solver.pdf , есть ли возможности масштабирования алгоритма?

Если кому-то влом читать статью, то там решались проблемы с размерностью
<quote> Time requirements to find all 7:77874 * 10^9
total output sets for the given input set, time required for the sequential
program is 19;211 seconds
<quoute>
Если я все правильно понял, то решать такое алгоритмом O(N^4) будет слишком больно.

Что означает точность O(N^4)?
не точность, а сложность.
Я так понимаю под N понимается количество входных множеств
да правильно понимаете.
как будет расти время выполнения в зависимости от размера входного множества?
как N^4, где N-кол-во строк
есть ли возможности масштабирования алгоритма?
если речь идет о распараллеливании, на потоки, ядра, компьютеры, то да можно нет проблем.
Как ваши результаты соотносятся с результатами из статьи
Цитата: We have used Donald Knuth’s «Algorithm X» and DLX
technique [6] to solve the exact cover problem. Ни как не соотносится у них алгоритм эвристиечкий, вот тута написано что это ru.wikipedia.org/...ческий_алгоритм
у меня алгоритм точный.
как N^4, где N-кол-во строк
Вы хотите сказать, что алгоритм работает одинаковое количество времени для четырех множеств, каждое из которых содержит 10^9 элементов и для четырех множеств, каждое из которых содержит 10^13 элементов?

Как подсказывает математика 5 класс, (10^9)^4=10^36, меньше чем (10^13)^4 =10^52. Так что не одинаковое.

Лол. Я вначале задал вопрос какая сложность алгоритма( ошибся только словом с бодуна, но был поправлен). Получил ответ O(N^4) ОТ КОЛИЧЕСТВА МНОЖЕСТВ. По Вашей логике, сложность в обоих случаях 4^4 — она не зависит от количества элементов в множестве.

ак будет расти время выполнения в зависимости от размера входного множества(тоесть задачи где десяток множеств, но в них по миллиарду елементов)?
как N^4, где N-кол-во строк
Первая цитата вопрос мой, вторая ответ Ваш. Теперь же Вы сами себе противоречете.

Смотрите, сложность решения находится в пределах O(N^4) где N — количество строк. Как показывают многочисленные опыты, реально время тратится на порядок меньше. Эта оценка O(N^4) она скорее ориентир на что надо расчитывать.

Это какой-то цирк. 4^4=16. Вы реально считаете, что если на входе будут 4 множества, в каждом из которых по 10^9 элементов то эта оценка верна? Советую чуть подумать перед тем как отвечать дабы не позориться.

Во первых 4^4=256. Во вторых если будет 4 строки по 10^9 элементов, это не страшно, совсем не страшно, очень быстро найдет)))). В-третьих что вы понимаете под операцией? Вот к примеру возьмем полный перебор, как понимаю я один из способов его осуществить это выбирать последовательно наборы строк, щас объясню, если у нас 4 строки, то 2^4 = 16 Есть 16 вариантов выбора строк −1, когда не выбрано ни одной строки, т.е. 0001,0010,0011,0100 и т.д.Вот если такого выбора операцию считать как операцию, без учета времени на проверку покрывают ли строки множество, которое да зависит от кол-ва элементов. Но дело в том что когда у нас будет 1000 срок, и 2^1000~=10^300, тогда линейная операция проверки покрытия перестает иметь значение, а имеет значение лишь кол-во вариантов которые надо перебрать.

не говоря уже о том что проверку покрытия можно легко реализовать на аппаратном уровне и она будет выполняться за такт(имею ввиду конечно на данном этапе развития электроники для не большого количества множеств в 10^9 элементов), но количество вариантов полного перебора увы не аппаратно не программно уменьшить не получится.

В-третьих что вы понимаете под операцией?
Когда вы пишете O(f(x)) то вы даете верхнюю оценку количеству элементарных операций для выполнения алгоритма. Под элементарными во всех местах где я бывал понимают операции +, -, /, *, побитовые операции, операции сравнения и т.д. Вот эти рассуждения о проделывании чего-то на аппаратном уровне можете оставить на то время, когда это будет сделано. А на данный момент вы пытаетесь выдать желаемое за действительное( может сам того не понимая)

Реальность такова, проверено многократно:
N=500, сложность должна быть 62*10^9, реально в 2000 раз быстрее. Это для сложных задач. Для простых задач ну пусть в 2млн раз быстрее чем оценка. Дайте пример, который выйдет за приделы оценки.

Сколько времени у вас решается задача, в которой 10 множеств, а в каждом из множеств по 10^12 элементов?

10^12*8байта = 8ТБ боюсь что в память не поместиться..... Не могу проверить.

вы неверно оперируете О() сложностью.
Она исключительно говорит о количестве повторений цикла алгоритма, пусть на это уходит и 1 час

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

Товарищ понимает и не такое ;) Но размер множеств для моего солвера не критичен.

m. Ни как не соотносится у них алгоритм эвристиечкий, вот тута написано что это
Там алгоритм недетерминнированный, а не эвристический. Тут можете почитать что это
en.wikipedia.org/...istic_algorithm
en.wikipedia.org/...mputer_science

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

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

Собственно сам алгоритм такой, что должен работать правильно, там нет возможности не правильно решения если оно есть, поверь я с лета 2000 года занимаюсь данной проблемой и понимаю о чем говорю.
По вашему пониманию когда, именно после этих слов, у людей не должно остаться никаких сомнений в верности вашего подхода и правдивости опубликованных вами замеров? Или, быть может, более формальные обоснования тоже имеются?
Во-первых, вы занимаетесь проблемой более десяти лет, и при этом у вас нет собственной реализации классического алгоритма
За чем мне реализация не работающего алгоритма? Во вторых я ведь не точным покрытие занимаюсь а этой тематикой. Точное покрытие я реализовал за последний месяц +/-.
Или, быть может, более формальные обоснования тоже имеются?
Скажем так — можно написать, но пока что в планы не входит раскрытие.
не работающего алгоритма
спасибо, больше вопросов не имею

Так это моя задача показать, что ваш алгоритм лучше хотя бы парочки уже существующих солверов или ваша?

Ну хорошо, я же говорю, что нашел солвер один здесь: code.google.com/.../downloads/list , больше не нашел, протестил, пришел к выводу что он и рядом не валялся. Если кто то знает солвер лучше чем нашел я, или чем сделал я, пожалуйста покажите. Кстати не плохой солвер предложил reality_hacker, исходник ниже. Правда пока что он проигрывает по памяти очень серьезно.

Запостите пример и посмотрим.

DOU — торт, один эпичный тред за другим :)

Приветствуется критика, и замечания по самому сайту
Английский на сайте очень плохой, думаю, стоит его подтянуть. Это пригодится и в будущем, при общении с коллегами из института Клэя, например.

Я кстати тут набодяжик экспоненциальный солвер на 20 строк, который рвет твой «полиномиальный» в 5 раз на твоем же тесте:

import java.nio.charset.Charset;
import java.nio.file.FileSystems;
import java.nio.file.Files;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
 
public class ExactCoverSolver {
  static Set<Integer> usedS = new HashSet<>();
  static Set<Long> usedAlphabet = new HashSet<>();
  static List<Set<Long>> S = new ArrayList<>();
  static Set<Long> alphabet = new HashSet<>();
 
  public static void main(String[] args) throws Exception {
    List<String> problemLines = Files.readAllLines(
        FileSystems.getDefault().getPath("sample_big.xct"),
        Charset.defaultCharset());
    for(int i = 1; i < problemLines.size(); i ++) {
      if(problemLines.get(i).startsWith("m")) {
        break;
      }
      Set<Long> subset = new HashSet<>();
      String entries[] = problemLines.get(i).split(" ");
      for(int j = 1; j < entries.length; j ++) {
        subset.add(Long.parseLong(entries[j]));
      }
      S.add(subset);
      alphabet.addAll(subset);
    }
   
    solve(0);
  }
 
  static void solve(int start) {
    if(usedAlphabet.size() == alphabet.size()) {
      System.out.println(usedS);
      return;
    }
    for(int i = start; i < S.size(); i ++) {
      if(!usedS.contains(i) && !usedInAlphabet(i)) {
        usedS.add(i);
        usedAlphabet.addAll(S.get(i));
        solve(i + 1);
        usedS.remove(i);
        usedAlphabet.removeAll(S.get(i));
      }
    }
  }
 
  static boolean usedInAlphabet(int i) {
    for(Long s: S.get(i)) {
      if(usedAlphabet.contains(s)) {
        return true;
      }
    }
    return false;
  }
}

я джаве не спец ине притендую, может быть что делаю не так, но:
C:\Program Files (x86)\Java\jre6\bin>java.exe ExactCoverSolver.java
Exception in thread “main” java.lang.NoClassDefFoundError: ExactCoverSolver/java
Caused by: java.lang.ClassNotFoundException: ExactCoverSolver.java
at java.net.URLClassLoader$1.run(Unknown Source)
at java.security.AccessController.doPrivileged(Native Method)
at java.net.URLClassLoader.findClass(Unknown Source)
at java.lang.ClassLoader.loadClass(Unknown Source)
at sun.misc.Launcher$AppClassLoader.loadClass(Unknown Source)
at java.lang.ClassLoader.loadClass(Unknown Source)
at java.lang.ClassLoader.loadClassInternal(Unknown Source)
Could not find the main class: ExactCoverSolver.java. Program will exit.

Лучше попробуй набрать:
javac ExactCoverSolver.java
java ExactCoverSolver yourinputfile

Уже разобрался. Хорошая заявка на победу. НО рекурсия не выход, память сжирает, и через несколько часов памяти не хватит даже у меня (32GB). У меня же память не увеличивается! Лови тест.

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

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

Памяти даже при рекурсии нужно O(n), где n — это множество подмножеств, т.е. в терминах О оверхеда по памяти в моем концепте нету.

Через 45 минут, у меня 22Мб, у тебя 370Мб, пока писал у тебя уже 430Мб, у меня без изменений.

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

Неа. GC запускается регулярно, скажем так чаще чем раз в минуту, и это я думаю для 1-го поколения, для нулевого там раз в секунду или чаще. Даже если ты прав то по умолчанию, если я правильно понял, памяти 512Мб может не очищать, но уже 570Мб используется. Более того плагин VisualGC показывает что память чистится на «ничего не делающей» VM. К сожалению пока не понял как подключиться к процессу который выполняется как class, не хочется останавливать и перезапускать.

Залил пример в 30 строк с того же сайта, но в ответ ни гу-гу. Бегло взглянул на код генератора тестов, но к ночи этого делать не стоило.

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

Дело в том что хостинг сам по себе слабый, в смысле проц медленный и памяти маловато, боюсь что он-лай в принципе не возможно. Что то считать будет, что то нет.

Плохому танцору всегда что-то мешает.

Неясна цель — это самопиар или что?
Вам дадут премию Тьюринга?

Приветствуется критика, и замечания по самому сайту.
сайт — дерьмо, неудобный и сверстан совершенно странно, наполнение куцее.
что бы проверить правильность работы, кто будет постить тесты, удаляйте пожалуйста все что после строки с маркером «m», включая саму строку.
бугага, нет валидации входных данных — подход на ура. Самому лень обрезать маркер?

исходный код выковыривать файлики из zip — очень профессионально, видимо .NET девелоперы не эволюционируют до github/bitbucket-а.

сайт — дерьмо, неудобный и сверстан совершенно странно, наполнение куцее.
не конструктивно
бугага, нет валидации входных данных
где именно?
исходный код выковыривать файлики из zip
в zip — только то что можно скачать с сайта, что не так?
могу разместить те исходники на github не вопрос.
сайт — дерьмо, неудобный и сверстан совершенно странно, наполнение куцее.
не конструктивно
где хотя бы блок-схема алгоритма?
Я уже не говорю о подробностях реализации, которую тоже было бы неплохо разместить на сайте.
где именно?
тут:
что бы проверить правильность работы, кто будет постить тесты, удаляйте пожалуйста все что после строки с маркером «m», включая саму строку.
и тут:
0 — быть не должно в данных строк, минимум цифра 1, генератор теста ведь этого не позволяет сделать.
и наверняка где-то еще.
где хотя бы блок-схема алгоритма?
Я уже не говорю о подробностях реализации, которую тоже было бы неплохо разместить на сайте.
не уверен что буду публиковать
тут:
что бы проверить правильность работы, кто будет постить тесты, удаляйте пожалуйста все что после строки с маркером «m», включая саму строку.
собственно для этого и дал исходник, правь как хочешь, может в отдельный файл сохранить решение. у меня файл читается без проблем. Но как то не хорошо будет если я получу решение. Хотя оно у меня у ни как не используется. Сделал что бы проверить просто было результат работы.
и тут:
0 — быть не должно в данных строк, минимум цифра 1, генератор теста ведь этого не позволяет сделать.
да согласен надо сделать валидацию. работы еще не початый край, главное что алгоритм работает.

Засунул небольшой файлик на 8 килобайт (по сравнению с 300МБ файлами в твоих тестах), уже 15 минут жду (вместо обещаных секунд), ответа все нету. ЧЯДНТ?

0 — быть не должно в данных строк, минимум цифра 1, генератор теста ведь этого не позволяет сделать.

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

Ты как и ожидалось какую то хню прислал.
1. По формулировке задачи ты должен прислать мне подмножество моих строк, ты прислал какие то свои сгенерированные.
2. По условию задачи твой результат должен покрывать все множество X, твой результат содержит только числа до 200, мой датасет содержит числа до 1000 включительно.

Ошибки нет. Это номера строк. Которые содержат числа, от 1 до 1000. Если взять все эти строки то получится покрытие множества от 1 до 1000.

Ок, продолжаем дальше, в твоем результате строки 2 и 11 содержат одно и тоже число 666 — по условию задачи такого быть не должно.

Строки считаются с нуля.

Откуда столько ненависти?

А как можно узнать что твой алгоритм всегда выдает правильный ответ?

Два аргумента: 1) я сделал очень много тестов, их результаты будут выложены на сайте на странице «Practical Results», просто руки не доходят это сделать. Все тесты завершились положительно. 2) Собственно сам алгоритм такой, что должен работать правильно, там нет возможности не правильно решения если оно есть, поверь я с лета 2000 года занимаюсь данной проблемой и понимаю о чем говорю. Кроме того просто сделай тест и пришли мне, ответ будешь знать только ты, если я дам тот же самый значит алгоритм правильный. Пока почему то ни кто не прислал, не понимаю почему.

вот была великая теорема ферма, и вроде и все тесты проходили, а математики все равно не могли успокоится, и 350 лет пытались строго ее доказать. К чему бы это?

Ферма не имеет сама по себе практического смысла.

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

Ферма не имеет сама по себе практического смысла.
Как-как? Нет, серьезно, вы можете это вот так написать — «теорема ферма не имеет сама по себе практического смысла»? Чтобы не было двусмысленных толкований предыдущей фразы.

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

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

Теорема Ферма косвенно повлияло на изучение эллиптических кривых. Если бы не было такого интереса к теореме Ферма кто знает на какой бы стадии сейчас было доказательство гипотезы Таниями-Шимуры.

Да разработанный при ее решении математический аппарат может быть весьма полезен.

Дмитрий, я немного побуду буквоедом
Во-первых — не «решении», а «доказательства».
Во-вторых — не «при», а «для».
И еще — под каждым сообщением есть ссылка «Ответить». Если на нее нажать, то ответ будет опубликован сразу под сообщением — «лесенкой», это удобнее для восприятия.

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

Досить цікаво) але думаю, якщо ти хочеш щоб тобі її спробували «зачаленджити» — краще запость на codeforces.ru або topcoder.com/tc

Подписаться на комментарии