Ads
AdBlock has stolen the banner, but banners are not teeth — they will be back

More

Comments 14

    +8
    Это троллинг?
      –3
      Да почему, я же не говорю, что классы равны, а этот алгоритм можно легко самому проверить
        +4
        Ну как. Вы либо говорите это, либо вводите людей в заблуждение заголовком.

        1. Если вы говорите, что ваш алгоритм полиномиальный и он решает NP-полную задачу, то вы утверждаете, что P=NP.
        2. Если поставленная задача не NP-полная, то вы утверждаете, что она принадлежит P. Доказательство этого факта никаким образом не приближает к решению задачи P vs. NP.
          –3
          Хорошо, на самом деле, я не знаю по поводу полноты этой задачи, давайте тогда так поступим, есть задача по поиску клики, она NP-полная, если мы поступим с задачей по поиску клики так же, как и в этой задачке, то максимальная клика находится по такому же алгоритму: https://pp.vk.me/c626723/v626723520/1693c/yrJf8r_pbBQ.jpg
          В примере в графе всего 5 клик, видно, что клика 1,2,3,4 является наибольшей, что доказывает и перебор и алгоритм
            +4
            В задаче о клике (которая является NP-полной) граф произвольной формы. Задача о максимальной клике без весов на ребрах в полносвязном графе очевидно решается за O(1). Тут задача maximum weighted clique в полносвязном графе (я сходу не уверен что она NP-полная, хочется почитать обоснование), и судя по всему предлагается ее решать жадным алгоритмом методом последовательного удаления вершин с минимальной суммарной стоимостью удаленных ребер, и все равно непонятно что делать если после удаления одной вершины получатся подклики одинакового суммарного веса и почему делается всего один шаг.
              0
              Можно взять произвольный граф, ребрам назначить вес 1, несуществующим рёбрам назначить вес -INF. Размер вырастет полиномиально. Клика с ребрами исходного графа даст максимальный вес.
          +3

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


          Ведь при положительном ответе, программисты смогут гораздо оптимизировать многие аспекты программы

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

            +4
            Думаю, автору тяжело будет продолжить дискуссию.
        +2
        Гениально. Срочно дуйте в институт Клея! (и это не опечатка!)
          +3
          а можно где-нибудь увидеть обоснование принадлежности этой задачи к классу NP?
            +3
            У вас в статье по ссылке гениальное заключение: P ⊂ NP. Скажу по секрету: мы все это и так знали.
              +1
              Нет там написано не так, так написано, что P ∈ NP — и у меня это вызывает вопрос, а что именно автор имеет ввиду под P (NP)?

              Другой вопрос касается формулы 5 почти в самом начале статьи (на которую дана ссылка), автор предлагает вычесть две матрицы размера nxn, а потом прибавить нулевую матрицу размера nx1, если я правильно понял обозначения… У меня вопрос, а как предлагается складывать матрицы разных размерностей? И что подразумевается под «нулевой» матрицей и как прибавление «нулевой» матрицы должно изменить результат?

              Наконец, неплохо бы иметь хоть какое-то обоснование этих формул, кроме загадочного упомянутого в статье анализа «случайно сгенерированных матриц размером 5x5».
              +1
              Спасибо за статью. Тема интересная и злободневная. Не исключено, что вы, автор, действительно нашли решение, над которым человечество бьется не один десяток лет. Но когда я пытался вникнуть в описание вашего метода, кое-что сразу бросилось в глаза, а именно — стилистика.
              Ведь при положительном ответе, программисты смогут гораздо оптимизировать многие аспекты программы,

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

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

              Слово «разных» здесь к чему относится? К тому, что графы удобнее рассматривать в виде матриц? Или к тому, что матричные представления могут быть разными? Или это просто лишнее слово в предложении?

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

              Теперь по сути дела. Известно, что NP-полные задачи сводятся одна к другой, в этом смысле все они эквивалентные. Поэтому считается, что если вы смогли решить одну такую задачу за полиномиальное время — то вы сможете решить их все. Остальные задачи нужно будет просто свести к той, для которой вы нашли эффективное решение. И методы приведения NP-полных задач одна к другой известны и описаны в литературе. Чтобы не ломать голову над каждой конкретной NP-полной задачей, вам достаточно решить какую-нибудь одну из них, любую. Остальное уже дело техники.

              Ну и для придания вашей статье убедительности вам необходимо показать, что:
              1) рассматриваемая вами задача является NP-полной;
              2) ваше решение работает, причем за полиномиальное время, для любой конфигурации рассматриваемой задачи.

              Понятно, что проверить решение «традиционными» методами для достаточно больших задач невозможно, но есть приближенные методы, всякие там «simulated annealing» и т.д. Для экспериментальной проверки вашего решения вам достаточно будет показать, что оно лучше или, по крайней мере, не хуже решений, полученных приближенными методами.
                0
                Нет постановки задачи.
                Каждый абзац(за редким исключением) со слов «теперь решение» порождает вопрос: «Почему так». Только после этого можно как-то продолжать дискуссию, касательно NP-полноты и т.д. Прошу, переделайте более формально (примеры оставьте), добавьте комментарии и пояснения к действиям, переход к другим задачам — вот тогда будет интересно и возможно разобраться в таком труде за адекватное время.

                Only users with full accounts can post comments. Log in, please.