Return to the
comp.compilers page.
Search the
comp.compilers archives again.
| Related articles |
|---|
| On CFL equivalence and graph isomorphism johnston.p@worldnet.att.net (Paul Johnston) (2000-04-20) |
| Re: On CFL equivalence and graph isomorphism lex@cc.gatech.edu (2000-04-25) |
| Re: On CFL equivalence and graph isomorphism colohan+@cs.cmu.edu (Christopher Brian Colohan) (2000-04-25) |
| Re: On CFL equivalence and graph isomorphism pmoisset@altavista.net (Pablo) (2000-04-25) |
| Re: On CFL equivalence and graph isomorphism ger@informatik.uni-bremen.de (George Russell) (2000-04-26) |
| Re: On CFL equivalence and graph isomorphism bdm@cs.anu.edu.au (2000-04-26) |
| Re: On CFL equivalence and graph isomorphism dmolnar@fas.harvard.edu (David A Molnar) (2000-04-27) |
| Re: On CFL equivalence and graph isomorphism miyazaki@symbolix.cs.uoregon.edu (2000-04-27) |
| From: | David A Molnar <dmolnar@fas.harvard.edu> |
| Newsgroups: | comp.theory,comp.compilers |
| Date: | 27 Apr 2000 10:41:50 -0400 |
| Organization: | Harvard University, Cambridge, Massachusetts |
| Distribution: | inet |
| References: | 00-04-140 00-04-167 00-04-184 |
| Keywords: | theory, parse |
In comp.theory Brendan McKay <bdm@cs.anu.edu.au> wrote:
> That might not be a correct statement even if the problem is
> NP-complete. It is a very common myth, though. The truth is that
> people solve real-life instances of NP-complete problems every day.
Yup. Just ask cryptographers trying to create cryptosystems based on
NP-complete problems...
Russell Impagliazzo has a neat paper related to this topic.
"A Personal View of Average Case Complexity"
http://www-cse.ucsd.edu/users/russell/average.ps
Thanks,
-David
[You're both right. It's often possible to get an approximate answer to
an NP complete problem that's good enough for many uses. But crypto
problems are deliberately designed so only the exact answer is useful.
-John]
Return to the
comp.compilers page.
Search the
comp.compilers archives again.