Loading ...
Sorry, an error occurred while loading the content.

Approach for attacking NP-complete problems?

Expand Messages
  • Omer Zak
    A problem is NP-complete because it can be represented as a recipe for generating several positions and scoring each of them, such that the recipe for scoring
    Message 1 of 7 , Aug 25, 2005
    • 0 Attachment
      A problem is NP-complete because it can be represented as a recipe for
      generating several positions and scoring each of them, such that the
      recipe for scoring a position has no relationship to the recipe which
      generates the position.

      The "no-relationship" assumption is one, which might be amenable to
      attack in some cases. If a mathematical method can be found to force a
      relationship between the position generator and the scoring function,
      then the problem is simplified from being NP-complete.

      For example, in the travelling salesman's problem, a position is
      represented as an ordered list of the cities which he visits.
      The score is the length of the road which he has to travel to visit all
      the cities.

      Would the following plan of attack on a NP-complete problem be fruitful
      for solving at least some of the NP-complete problems?

      Let's use the travelling salesman's problem as an example.
      Starting from a given ordered list of N cities, compute its score.

      Now, form N(N-1)/2 lists, each formed by swapping two different cities
      in the original list. Compute the score for eah of the modified lists.

      The range of possible scores around the score of the original list is a
      subset of the range of possible scores over all N! lists. The question
      is whether it is possible to establish upper and lower bounds on the
      range of scores of the chosen list and its N(N-1)/2 variants, which are
      significantly restricted relative to the bounds of the range of scores
      over all N! lists. And if yes, how helpful would those bounds be at
      finding the list yielding the maximum score?
      --- Omer
      --
      Every good master plan involves building a time machine. Moshe Zadka
      My own blog is at http://www.livejournal.com/users/tddpirate/

      My opinions, as expressed in this E-mail message, are mine alone.
      They do not represent the official policy of any organization with which
      I may be affiliated in any way.
      WARNING TO SPAMMERS: at http://www.zak.co.il/spamwarning.html
    • Arik Baratz
      ... Hey choo, not proven yet not disproven. Your determination of the wasteness of the time relies on your baseless belief in its truth - just a belief, not a
      Message 2 of 7 , Aug 25, 2005
      • 0 Attachment
        On 25/08/05, guy keren <choo@...> wrote:

        > i think that discussing such issues on hackers-il should be banned,
        > on the grounds of "complete waste of time". ;)

        Hey choo, not proven yet not disproven. Your determination of the
        wasteness of the time relies on your baseless belief in its truth -
        just a belief, not a fact. Although I share that belief, let the
        heathens speak their mind lest they claim religious favoritism.

        -- Arik
      • Omer Zak
        ... Fermat s last theorem was an open problem for longer time, until it was finally solved. The mathematical tools needed to accomplish this feat would
        Message 3 of 7 , Aug 25, 2005
        • 0 Attachment
          On Thu, 2005-08-25 at 11:19 +0300, guy keren wrote:
          > the nice thing about NP-completeness, is that it holds this open
          > scientific problem since around 1973.

          Fermat's last theorem was an open problem for longer time, until it was
          finally solved. The mathematical tools needed to accomplish this feat
          would probably be found to be useful in other endeavors as well.

          > do you mean to tell us that you just thought of another idea of how to
          > prove that P=NP?

          No. Some NP-complete problems may turn out to be easier to solve than
          other NP-complete problems, depending on the relationship between
          position generation and position scoring functions; where some rigorous
          way to expreess this relationship needs to be found.

          > i think that discussing such issues on hackers-il should be banned,
          > on the grounds of "complete waste of time". ;)

          Oh, the usual resistance of Establishment scientists to the noise made
          by crackpot disestablishmentarian scientists. Besides, Jara Cimrman
          already solved the NP-complete problem in its full generality, but his
          notes were lost during World War I. :-)
          --- Omer
          --
          Jara Cimrman. A name to remember.
          My own blog is at http://www.livejournal.com/users/tddpirate/

          My opinions, as expressed in this E-mail message, are mine alone.
          They do not represent the official policy of any organization with which
          I may be affiliated in any way.
          WARNING TO SPAMMERS: at http://www.zak.co.il/spamwarning.html
        • guy keren
          the nice thing about NP-completeness, is that it holds this open scientific problem since around 1973. do you mean to tell us that you just thought of another
          Message 4 of 7 , Aug 25, 2005
          • 0 Attachment
            the nice thing about NP-completeness, is that it holds this open
            scientific problem since around 1973.

            do you mean to tell us that you just thought of another idea of how to
            prove that P=NP?

            i think that discussing such issues on hackers-il should be banned,
            on the grounds of "complete waste of time". ;)

            --guy

            On Thu, 25 Aug 2005, Omer Zak wrote:

            > A problem is NP-complete because it can be represented as a recipe for
            > generating several positions and scoring each of them, such that the
            > recipe for scoring a position has no relationship to the recipe which
            > generates the position.
            >
            > The "no-relationship" assumption is one, which might be amenable to
            > attack in some cases.If a mathematical method can be found to force a
            > relationship between the position generator and the scoring function,
            > then the problem is simplified from being NP-complete.
            >
            > For example, in the travelling salesman's problem, a position is
            > represented as an ordered list of the cities which he visits.
            > The score is the length of the road which he has to travel to visit all
            > the cities.
            >
            > Would the following plan of attack on a NP-complete problem be fruitful
            > for solving at least some of the NP-complete problems?
            >
            > Let's use the travelling salesman's problem as an example.
            > Starting from a given ordered list of N cities, compute its score.
            >
            > Now, form N(N-1)/2 lists, eachformed by swapping two different cities
            > in the original list.Compute the score for eah of the modified lists.
            >
            > The range of possible scores around the score of the original list is a
            > subset of the range of possible scores over all N! lists.The question
            > is whether it is possible to establish upper and lower bounds on the
            > range of scores of the chosen list and its N(N-1)/2 variants, which are
            > significantly restricted relative to the bounds of the range of scores
            > over all N! lists.And if yes, how helpful would those bounds be at
            > finding the list yielding the maximum score?
            > --- Omer
            >

            --
            guy

            "For world domination - press 1,
            or dial 0, and please hold, for the creator." -- nob o. dy
          • guy keren
            ... my determination that this is a waste of time comes from a different angle - that this issue was discussed to death for over 30 years and still was not
            Message 5 of 7 , Aug 25, 2005
            • 0 Attachment
              On Thu, 25 Aug 2005, Arik Baratz wrote:

              > On 25/08/05, guy keren <choo@...> wrote:
              >
              > > i think that discussing such issues on hackers-il should be banned,
              > > on the grounds of "complete waste of time". ;)
              >
              > Hey choo, not proven yet not disproven. Your determination of the
              > wasteness of the time relies on your baseless belief in its truth -
              > just a belief, not a fact. Although I share that belief, let the
              > heathens speak their mind lest they claim religious favoritism.

              my determination that this is a waste of time comes from a different angle
              - that this issue was discussed to death for over 30 years and still was
              not solved. statistically, it would not be solved this time, too. hackers
              are pragmatic people - trying to solve such open problems should be left
              to the romantics ;) it might be solved one day, but then again, someone
              might prove that there is no possibility to solve this (godel is with me
              on the possibility for this to be done...).

              so no, don't try to guess what my belief is.
              i'm simply being pragmatic.

              --
              guy

              "For world domination - press 1,
              or dial 0, and please hold, for the creator." -- nob o. dy
            • guy keren
              ... and it was not solved by a hobbist hacker, was it? :P~~ the days when hobbists were able to change the face of math in a fortnight are long since gone, i m
              Message 6 of 7 , Aug 25, 2005
              • 0 Attachment
                On Thu, 25 Aug 2005, Omer Zak wrote:

                > On Thu, 2005-08-25 at 11:19 +0300, guy keren wrote:
                > > the nice thing about NP-completeness, is that it holds this open
                > > scientific problem since around 1973.
                >
                > Fermat's last theorem was an open problem for longer time, until it was
                > finally solved.The mathematical tools needed to accomplish this feat
                > would probably be found to be useful in other endeavors as well.

                and it was not solved by a hobbist hacker, was it? :P~~

                the days when hobbists were able to change the face of math in a fortnight
                are long since gone, i'm afraid. the last one that did somehting like this
                was killed in a duel the day after writing his essay ;)

                > > do you mean to tell us that you just thought of another idea of how to
                > > prove that P=NP?
                >
                > No.Some NP-complete problems may turn out to be easier to solve than
                > other NP-complete problems, depending on the relationship between
                > position generation and position scoring functions; where some rigorous
                > way to expreess this relationship needs to be found.

                perhaps you don't understand what NP-complete is, then. all NP-complete
                problems are "hard to solve" on the same level. this is the _definition_
                of NP-complete - that there's a reduction from any problem in NP space to
                the given problem - that's what differentiates an NP-complete problem from
                a general NP problem.

                > > i think that discussing such issues on hackers-il should be banned,
                > > on the grounds of "complete waste of time". ;)
                >
                > Oh, the usual resistance of Establishment scientists to the noise made
                > by crackpot disestablishmentarian scientists.Besides, Jara Cimrman
                > already solved the NP-complete problem in its full generality, but his
                > notes were lost during World War I.:-)

                i am not an established scientists. i left the persuit of that position 13
                years ago.

                --
                guy

                "For world domination - press 1,
                or dial 0, and please hold, for the creator." -- nob o. dy
              • Ofir Carny
                If I understand correctly, you describe NP, not NP-complete. As to the methodology, if a problem is indeed NP-complete, it would only work for specific cases
                Message 7 of 7 , Aug 28, 2005
                • 0 Attachment
                  If I understand correctly, you describe NP, not NP-complete. As to the methodology, if a problem is indeed NP-complete, it would only work for specific cases or in approximation, which will not provide anything new to computer science.

                  On 8/25/05, Omer Zak <omerz@...> wrote:
                  A problem is NP-complete because it can be represented as a recipe for
                  generating several positions and scoring each of them, such that the
                  recipe for scoring a position has no relationship to the recipe which
                  generates the position.

                  The "no-relationship" assumption is one, which might be amenable to
                  attack in some cases.  If a mathematical method can be found to force a
                  relationship between the position generator and the scoring function,
                  then the problem is simplified from being NP-complete.

                  For example, in the travelling salesman's problem, a position is
                  represented as an ordered list of the cities which he visits.
                  The score is the length of the road which he has to travel to visit all
                  the cities.

                  Would the following plan of attack on a NP-complete problem be fruitful
                  for solving at least some of the NP-complete problems?

                  Let's use the travelling salesman's problem as an example.
                  Starting from a given ordered list of N cities, compute its score.

                  Now, form N(N-1)/2 lists, each formed by swapping two different cities
                  in the original list.  Compute the score for eah of the modified lists.

                  The range of possible scores around the score of the original list is a
                  subset of the range of possible scores over all N! lists.  The question
                  is whether it is possible to establish upper and lower bounds on the
                  range of scores of the chosen list and its N(N-1)/2 variants, which are
                  significantly restricted relative to the bounds of the range of scores
                  over all N! lists.  And if yes, how helpful would those bounds be at
                  finding the list yielding the maximum score?
                                                                 --- Omer
                  --
                  Every good master plan involves building a time machine.  Moshe Zadka
                  My own blog is at http://www.livejournal.com/users/tddpirate/

                  My opinions, as expressed in this E-mail message, are mine alone.
                  They do not represent the official policy of any organization with which
                  I may be affiliated in any way.
                  WARNING TO SPAMMERS:  at http://www.zak.co.il/spamwarning.html



                  ------------------------ Yahoo! Groups Sponsor --------------------~-->
                  <font face=arial size=-1><a href=" http://us.ard.yahoo.com/SIG=12h8oc6rt/M=362131.6882499.7825260.1510227/D=groups/S=1705006764:TM/Y=YAHOO/EXP=1124962016/A=2889191/R=0/SIG=10r90krvo/*http://www.thebeehive.org
                  ">Get Bzzzy! (real tools to help you find a job) Welcome to the Sweet Life -brought to you by One Economy</a>.</font>
                  --------------------------------------------------------------------~->


                  Yahoo! Groups Links

                  <*> To visit your group on the web, go to:
                      http://groups.yahoo.com/group/hackers-il/

                  <*> To unsubscribe from this group, send an email to:
                       hackers-il-unsubscribe@yahoogroups.com

                  <*> Your use of Yahoo! Groups is subject to:
                      http://docs.yahoo.com/info/terms/




                Your message has been successfully submitted and would be delivered to recipients shortly.