Path: utzoo!utgpu!watmath!maytag!water!ymchee
From: ymchee@water.waterloo.edu (Yeow Meng Chee)
Newsgroups: comp.graphics
Subject: Re: plotter optimizing algorithm
Message-ID: <2271@water.waterloo.edu>
Date: 25 Apr 89 00:25:47 GMT
References: <633@jc3b21.UUCP> <863@mplvax.EDU> <SARREL.89Apr24143841@dory.cis.ohio-state.edu>
Organization: U of Waterloo, Ontario
Lines: 18

In article <SARREL.89Apr24143841@dory.cis.ohio-state.edu>, sarrel@dory.cis.ohio-state.edu (Marc Sarrel) writes:
> It occurs to me that the famous "travelling salesman" problem, which
> we know to be NP-Complete, might reduce to the pen plotter
> optimization problem.  If the pen optimization problem is, therefore,
> NP-Complete, it cannot be solved in non-deterministic polynomial time.
>  		  ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
> (assuming that P != NP) .....

Of course the problem could be solve in non-deterministic polynomial time
(independent of whether P=NP or not). That is what NP is all about.
Please read Garey and Johnson to understand what the notion of NP means!

*************************************************************
Yeow Meng Chee; Department of Computer Science;
Faculty of Mathematics; University of Waterloo;
Waterloo, Ontario, Canada  N2L 3G1
{ymchee@water.bitnet; ymchee@water.uwaterloo.ca}
Good Day eh!