I believe that a polynomial solution to the Logical Satisifiability problem will have a major effect on AI, and I would like to discuss that at sometime.
Jim Bromer Richard Loosemore <[EMAIL PROTECTED]> wrote: 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 /* 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/?&; > ----- 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/?&; --------------------------------- 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=87920434-59ad4a
