--- Jim Bromer <[EMAIL PROTECTED]> wrote: > 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.
This is an example of a problem which is not in NP. A problem is in NP if a solution can be verified in polynomial time. A problem is in P if the solution can be found in polynomial time. By polynomial, I mean that in the worst case, the time is a polynomial function of the size of the input. For example the SAT problem is to determine if there is a variable assignment that evaluates to true, and if so, output a variable assignment. The traveling salesman problem (TSP) is, given a graph and a number D, to determine if there is a cycle of length D or less that visits each vertex exactly once, and if so, output the cycle. SAT and TSP are NP-complete. That means any problem in NP can be solved by calling one of these problems as a subroutine by a program that is otherwise in P. Thus, if SAT or TSP is in P, then all problems in NP are also in P, in which case P=NP. There are over 3000 problems known to be NP-complete. If any one of them can be solved in polynomial time, then they all can. It is widely believed that P!=NP because a lot of people have tried and failed to do this. However, it is not proven that P!=NP. The Clay Institute has offered a $1 million prize for a proof either way. A partial list of problems can be found here: http://en.wikipedia.org/wiki/List_of_NP-complete_problems Good luck. -- Matt Mahoney, [EMAIL PROTECTED] ----- 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=87672524-64fc61
