Matching ordinary regular expresions can be done in polynomial time, proportional to MN, where M is the length of the regular expression and N is the length of the string to be matched. The usual method for this is: Parse the regular expression and construct an equivalent finite automaton (FA), which will have O(M) states; then simulate the action of the FA on the input, which takes O(MN) time. My Regex.pm module demonstrates this.
However, adding backreferences to regular expressions complicates them so that the usual FA construction does not work. Perl can handle these extended regexes, but it sometimes takes a long time to find out if there is a match or not. For example, Perl takes exponential time (in the length of the string to be matched) to check whether or not a string matches the regex /^(?:(\d+)|::)*$/.
One is tempted to wonder whether this difficulty is inherent, or whether there might be a clever way of speeding up the matching algorithm. The answer is that there is probably no clever way to speed up the algorithm, and that the exponential running time of the matching algorithm is probably unavoidable. We show below that regex matching is NP-hard when regexes are allowed to have backreferences.
The usual method of showing that a problem P is NP-hard is by showing that some other NP-hard problem, Q, could be solved efficiently if P could be also. I showed that instances of the GRAPH 3-COLORABILITY problem can be reduced to instances of regex matching. Abigail showed that instances of the 3CNF-SAT problem can be reduced to instances of regex matching. Greg Bacon showed that instances of the CLIQUE problem can be reduced to instances of regex matching.
This page used to say "Regex Matching is NP-Complete". That may not be correct. I've been meaning to fix it for years, but I never got around to it before. To show that regex matching is NP-complete, we need to show two things. First, we need to show that it is NP-hard; the proofs on this page do that. Second, we need to show that regex matching is in NP. The proofs don't do that.
Return to: Universe of Discourse main page | What's new page | Perl Paraphernalia
| 蛋白质被消化成什么 | instagram是什么 | 羊字五行属什么 | 尿路感染吃什么药好得快 | 什么肠小道成语 |
| 坐月子吃什么补气血 | 胚胎是什么 | 晚上12点是什么时辰 | 肾结石吃什么水果 | 三餐两点什么意思 |
| 糟卤是什么 | 梦见着火是什么预兆 | 什么样的孕妇容易翻盘 | 梦见理发是什么意思 | jimmy是什么意思 |
| 作奸犯科是什么意思 | 什么病不能吃空心菜 | loves是什么意思 | 西游记告诉我们什么道理 | 81年属鸡的是什么命 |
| 健康管理师是干什么的hcv8jop2ns2r.cn | 初遇是什么意思hcv9jop4ns6r.cn | 头发汗多是什么原因hcv8jop9ns9r.cn | 小甲鱼吃什么zhongyiyatai.com | 皮肤溃烂用什么药治愈最快gysmod.com |
| 翡翠什么样的好hcv9jop0ns0r.cn | 亲友是什么意思hcv7jop7ns4r.cn | 沮丧是什么意思gysmod.com | 不知道干什么hcv9jop3ns0r.cn | 什么是hcv7jop6ns7r.cn |
| 口腔溃疡是缺什么维生素hanqikai.com | 36d什么意思hcv8jop8ns9r.cn | 活水是什么意思hcv7jop6ns1r.cn | 扁桃体肿大吃什么药hcv8jop4ns9r.cn | 一代明君功千秋是什么生肖hcv8jop7ns4r.cn |
| 做梦梦到别人死了是什么征兆chuanglingweilai.com | 黄连治什么病最好hcv7jop9ns3r.cn | 狗狗胰腺炎有什么症状hcv8jop1ns5r.cn | 拉血是什么病baiqunet.com | SEX是什么hcv9jop4ns4r.cn |