Perl 6 - the future is here, just unevenly distributed

IRC log for #marpa, 2017-08-16

| Channels | #marpa index | Today | | Search | Google Search | Plain-Text | summary

All times shown according to UTC.

Time Nick Message
01:52 ilbot3 joined #marpa
01:52 Topic for #marpa is now Start here: http://savage.net.au/Marpa.html - Code paste/run: https://f.perlbot.pl/#marpa - Jeffrey's Marpa site: http://jeffreykegler.github.io/Marpa-web-site/ - IRC log: http://irclog.perlgeek.de/marpa/today - Youtube channel: https://www.youtube.com/channel/UCYKVfGBtfTqbs1JdYq-dc5g
05:28 ronsavage joined #marpa
07:25 ronsavage joined #marpa
17:32 idiosyncrat joined #marpa
17:34 idiosyncrat https://t.co/5e8InTb8m4
17:35 idiosyncrat Norbert Blum (a Bonn CS professor, not the politician) has claimed a proof that P != NP
17:36 idiosyncrat It's the most serious such claim in a while, and nothing obviously wrong has been found, but folks are reserving judgment.
17:37 idiosyncrat Blum's work is based on stuff I studied, but the field has progressed and the paper goes waaaaay beyond my current knowledge.
17:38 idiosyncrat OTOH Blum has published in parsing -- an LR(k) parser.
17:39 idiosyncrat LR(k) is a smaller class than the grammars Marpa/Leo parses in linear time, and Blum's parsers does not have Marpa's nice online and error-handling properties, or it's ability to parse ambiguous grammars.
17:41 idiosyncrat But worst of all the size of Blum's LR(k) parser is O(2**k) -- exponential in k.
17:42 idiosyncrat Going from LR(0) to LR(1) buys a lot, but from LR(1) to LR(2) you gain (in practice) very little, and it goes rapidly downhill.  This means your parsers are increasing exponentially in size for a small and rapidly diminishing return.
17:45 idiosyncrat https://arxiv.org/abs/1511.05770
17:46 idiosyncrat The above link is Blum
17:46 idiosyncrat 's LR(k) paper
17:47 idiosyncrat Most negative commentary on the Blum N != NP proof by mathematicians is in fact amateur sociology at this point -- the proof is too small so it would have already been found, etc, etc.
17:48 idiosyncrat I know from my work on parsing that marvelous and relatively simple results can easily remain undiscovered -- in Leo's case for years after he published it!
17:48 idiosyncrat (I note Blum's parsing paper cites Earley but shows no sign he was aware of Leo's work.)
17:51 idiosyncrat So I agree the odds are against Blum, but they are not hopeless and I'm rooting for him!  It looks like Blum's N != NP would be relatively easy to learn (the reason some folks at the moment are suspicious of it) and that'd make it a wonderful new contribution to what Erdos called "The Book".
22:51 ronsavage joined #marpa

| Channels | #marpa index | Today | | Search | Google Search | Plain-Text | summary