People say that regex with backreference matching is exponential or some such scary thing but how come it is so 
Follow
@koakuma You can reduce problems that are NPC to that. E.g. for 3SAT consider a string that is equal to "01" repeated 2*num_var or so times, "#", "%001%010%011%100%101%110%111" repeated n_clauses times and a regex that goes "(.)(.).*" repeated n_vars times, "#", ".*%\a\b\c.*" repeated for each clause, with a, b, c replaced with 2* identifiers of variables in that clause, incremented by 1 if the variables appears negated.
