<p>Thanks to <a href="https://cstheory.stackexchange.com/questions/47058/are-all-regexp-solvable-in-on#comment104496_47058">@emil's comment</a> and <a href="https://stackoverflow.com/a/13356328/1950267">this</a> stackoverflow answer, I now know that <a href="https://regular-expressions.mobi/posix.html?wlr=1" rel="nofollow noreferrer">POSIX extended regular expressions</a> are solvable in O(n) but backreferences are at least NP-hard and maybe NP-complete.</p>

CC BY-SA 4.0
2020-06-18T23:25:01.473Z
2020-06-18T23:25:01.473Z
Armin
<p>I'm wondering if all features, that are often part of modern RegEx engines, are solvable in O(n). I'm talking about features like repeating patterns <code>([abc]+);\1</code> would match <code>abc;abc</code> but not <code>abc;cba</code>, lazy or not greedy repetition operators <code>[ab]+?ba$</code> would match <code>abba</code> or <code>aaaabbbbba</code> but not <code>ababa</code>.</p>
<p>I know that things like anchors (<code>^</code> and <code>$</code>), optional operator (<code>a?</code>), character classes (<code>[abc]</code>, or <code>[^abc]</code>) and the plus operator can be reduced to nominal regex operations or are simple checks in the end.</p>

CC BY-SA 4.0
2020-06-18T05:45:41.967Z
https://perl.plover.com/NPC/ , https://hal.inria.fr/inria-00176043/
Emil Jeřábek
CC BY-SA 4.0
2020-06-18T18:30:45.070Z
do you have a reference that defines the extended RegExp? Can't figure it out from your post.
AmeerJ
CC BY-SA 4.0
2020-06-18T23:19:36.053Z
@AmeerJ the combination of Emil's comment and this https://stackoverflow.com/a/13356328/1950267 already answers my question pretty much. I've found the stackoverflow link while looking for a specification of extended RegExp...
Armin
<complexity-classes><regular-expressions>
Are all RegExp solvable in O(n)?
Armin
# Are all RegExp solvable in O(n)?

(Asked by: username_0 on 2020-06-18)

I'm wondering if all features, that are often part of modern RegEx engines, are solvable in O(n). I'm talking about features like repeating patterns `([abc]+);\1` would match `abc;abc` but not `abc;cba`, lazy or not greedy repetition operators `[ab]+?ba$` would match `abba` or `aaaabbbbba` but not `ababa`.

I know that things like anchors (`^` and `$`), optional operator (`a?`), character classes (`[abc]`, or `[^abc]`) and the plus operator can be reduced to nominal regex operations or are simple checks in the end.

**Tags:** complexity-classes, regular-expressions

> **Comments:**
> **username_1**: https://perl.plover.com/NPC/ , https://hal.inria.fr/inria-00176043/  
> **username_2**: do you have a reference that defines the extended RegExp? Can't figure it out from your post.  
> **username_0**: @username_2 the combination of Emil's comment and this https://stackoverflow.com/a/13356328/1950267 already answers my question pretty much. I've found the stackoverflow link while looking for a specification of extended RegExp...  

---

## 1 answers

### Answer by username_0 on 2020-06-18. Score: 3 | Accepted answer

Thanks to [@emil's comment](https://cstheory.stackexchange.com/questions/47058/are-all-regexp-solvable-in-on#comment104496_47058) and [this](https://stackoverflow.com/a/13356328/1950267) stackoverflow answer, I now know that [POSIX extended regular expressions](https://regular-expressions.mobi/posix.html?wlr=1) are solvable in O(n) but backreferences are at least NP-hard and maybe NP-complete.


---

