Robin Gane-McCalla <[EMAIL PROTECTED]> wrote: Can you give me an example of any
such problems (or a class of such problems)? By the definition of NP-complete,
any problem in NP must be reducible to any problem in NP through a polynomial
transformation.
---------------------------------------------------------
It took me a while to figure this one out. I was using the term np as a
measure of the time (or time-data space) for computational processes and it was
not very precise as such. However, the definition of np is more precise which
is why your comment forced me to think about it.
I was just trying to point out that even if a np-complete program was proven to
be solvable in p-time, there still would be problems that would take much
longer to solve. And some of them might look like np-complete problems to the
casual onlooker.
For instance the SAT problem asks only if a certain logical formula has a
solution (that is, a True solution). At this time, in the worse case the
solution to this problem for n variables could take more than 2^n 'steps' to
complete, which is the same time it would take to try every possible
combination of logical (True or False) values in the formula.
Let's say that a method (might as well say my method) produces a solution to
the SAT problem where even the worse cases can be determined in polynomial time.
Now let's say that the problem is not to determine whether or not there is a
solution or not, but to output every possible combination of values for a
logical formula and give the logical result as well. Since there are 2^n
combinations for a formula of n distinct logical variables, the output would
have to take more than 2^n 'steps'. So even supposing the np-complete problem
could be solved in polynomial time, there are still problems that cannot be
completed in polynomial time.
Interestingly, if a polynomial time solution to the SAT problem was found, it
might be possible to output a couple of formulas that could define all of the
true and all of the false combinations without distinctly outputting every one
separately. However, the problem I defined above specifically called for each
possible combination to be output and therefore it cannot be solved in
polynomial time -by definition-. This is a trivial example, but it shows that
there are problems that cannot be solved in polynomial time, and because this
problem has something in common with the np-complete problem of Satisfiability,
some people might be confused by the problem.
Jim Bromer
---------------------------------
Never miss a thing. Make Yahoo your homepage.
-----
This list is sponsored by AGIRI: http://www.agiri.org/email
To unsubscribe or change your options, please go to:
http://v2.listbox.com/member/?member_id=8660244&id_secret=87656165-3e9fe5
