Subject: Approach for attacking NP-complete problems?

From: Omer Zak <[email-masked]>
Date: Thu, 25 Aug 2005 10:19:44 +0300

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

---

From: guy keren <[email-masked]>
Date: Thu, 25 Aug 2005 11:19:44 +0300 (IDT)

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:

> attack in some cases.If a mathematical method can be found to force a
> 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.
>
> subset of the range of possible scores over all N! lists.The question
> over all N! lists.And if yes, how helpful would those bounds be at

-- 
guy

"For world domination - press 1,
 or dial 0, and please hold, for the creator." -- nob o. dy

---

From: Arik Baratz <[email-masked]>
Date: Thu, 25 Aug 2005 00:43:00 -0700

> 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

---

From: guy keren <[email-masked]>
Date: Thu, 25 Aug 2005 11:31:39 +0300 (IDT)

> 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

---

From: Omer Zak <[email-masked]>
Date: Thu, 25 Aug 2005 11:08:37 +0300

> 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

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.

> 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/

---

From: guy keren <[email-masked]>
Date: Thu, 25 Aug 2005 16:38:01 +0300 (EET DST)

On Thu, 25 Aug 2005, Omer Zak wrote:

> finally solved.The mathematical tools needed to accomplish this feat

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 ;)

> No.Some NP-complete problems may turn out to be easier to solve than

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.

> by crackpot disestablishmentarian scientists.Besides, Jara Cimrman
> notes were lost during World War I.:-)

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

-- 
guy

---

From: Ofir Carny <[email-masked]>
Date: Sun, 28 Aug 2005 12:36:23 +0200

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 <[email-masked]> wrote:
> Yahoo! Groups Links