Since P is a subset of NP, clearly there are problems in NP that can be solved in polynomial time. NP problems must be solvable by a non-deterministic Turing machine (in simple terms a turing machine that executes multiple actions for each symbol but only chooses the symbols which lead to an accept state) in polynomial time and have their solutions verified by a deterministic turing machine in polynomial time. NP-complete problems are just problems for which no polynomial time deterministic turing machine algorithm is known. All that is required to prove P = NP is to prove that NP is a subset of P, which would require finding a polynomial time algorithm for solving any problem which is NP-complete.
As for your problem involving SAT, it's not applicable to P-NP because they are classes of decisions problems (http://en.wikipedia.org/wiki/Decision_problem), which means problems that can be answered yes or no. And what you quoted should have been By the definition of NP-complete, any problem in NP must be reducible to any problem in NP-COMPLETE through a polynomial transformation. On Jan 18, 2008 1:47 PM, Jim Bromer <[EMAIL PROTECTED]> 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. > ________________________________ > > 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/?&; -- Robin Gane-McCalla YIM: Robin_Ganemccalla AIM: Robinganemccalla ----- 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=87666358-4e313e
