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