Because NEXP means non-deterministic exponecial , what is another class of problems, but NEXP problems are not so common in practice tahn NP problems.
The answer to your question is that, because for each NP problem there exist deterministic polynomial time algorithm, that can verify whether a given polynomial sized solution to that problem is correct. AFAIK NP was defined first through Turing machines. On Wed, Nov 5, 2008 at 7:48 PM, crypter00 <[EMAIL PROTECTED]> wrote: > > But then why NP means Non-deterministic Polynomial time etc.. > > > On Nov 4, 4:59 am, "[EMAIL PROTECTED]" <[EMAIL PROTECTED]> > wrote: > > There is only one known relation, and it is that each NP problem can > > be solved by exponential time algorithm. > > "Is there problem that is not in NP but have exponential solution" = > > Open problem. > > > > On 4. Nov, 06:39 h., crypter00 <[EMAIL PROTECTED]> wrote: > > > > > > > > > Is there any relation between algorithms that takes exponential time > > > and NP problems.- Hide quoted text - > > > > - Show quoted text - > > > --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
