This thread has nothing to do with artificial general intelligence: is
there not a more appropriate venue for it?
Richard Loosemore
Jim Bromer wrote:
*/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.
<http://us.rd.yahoo.com/evt=51438/*http://www.yahoo.com/r/hs>
------------------------------------------------------------------------
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/?&;
<http://v2.listbox.com/member/?&;>
-----
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=87706295-f6d33b
