2 ms·
No. Regular expressions plus backwards references is in NP; Turing machines can solve far more difficult decision problems.
by cperciva 19y ago
No. Regular expressions plus backwards references is in NP; Turing machines can solve far more difficult decision problems.
- eru 19y agoYes, they can. I was just to lazy to look this up myself. Thanks.