Re: On CFL equivalence and graph isomorphism

David A Molnar <dmolnar@fas.harvard.edu>
27 Apr 2000 10:41:50 -0400

          From comp.compilers

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)
| List of all articles for this month |

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]





Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.