--- Robin Gane-McCalla <[EMAIL PROTECTED]> wrote: > NP-complete problems are just problems for which no > polynomial time deterministic turing machine algorithm is known.
I believe that if P != NP then there could be problems "in between" that are not in P and also not NP-complete. However there is no proof of their existence because there is no proof that P != NP. > 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. In my last post, I described SAT and other NP-complete problems as function problems, where if the answer is yes it also outputs a witness, which would allow the answer to be proven in polynomial time. For example, SAT would output a satisfying variable assignment if the answer is yes. Verifiability on a deterministic Turing machine is equivalent to solving the decision problem on a nondeterministic machine, but I think a little easier to understand. -- 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=87676110-9de2b4
