Re: [mind game] Seeking for simple task impossible via regexps
[
Date Prev][
Date Next][
Thread Prev][
Thread Next]
[
Date Index]
[
Thread Index]
- Subject: Re: [mind game] Seeking for simple task impossible via regexps
- From: Dirk Laurie <dirk.laurie@...>
- Date: 2017年2月24日 14:56:01 +0200
2017年02月24日 14:28 GMT+02:00 Roberto Ierusalimschy <roberto@inf.puc-rio.br>:
> because of back references, Perl's regexs are NP-complete: you can code
> any NP problem as a regex plus a subject string (in polynomial time) and
> Perl will solve the problem (not in polynomial time :-).
>
> http://perl.plover.com/NPC/NPC-3SAT.html
To all those poets and artists who pity mathematicans and computer
scientists as soulless geeks who cannot comprehend beauty: this result,
in the words of one of your own number, is beauty bare.