| As always, with all these things, there's a non-zero chance that I've mis-spoken myself somewhere. I'm going to "think out loud" on this so people can follow the thought processes. > I read it the other way: OK ... > all CNF instances can be rewritten as regexp + backreferences, By CNF you are referring to instances of the SAT problem. So yes, if you have an instance of the SAT problem, it can be re-written as an instance of regex+backtrack. > meaning re + backreferences are at least as general that SAT, Yes, the regex+backtrack problem is at least as hard as the SAT problem. > ... not at most as. Where did I say that? Here's a stripped-down summary of my comment: * SAT is NP-Hard. * Now someone has shown that they can solve SAT problems by using regex+backtrack. (That's the linked article) * Thus regex+backtrack is at least as hard as every NP problem. * SAT is NP, so it's NPC * regex+backtrack can be seen to be in NP. * So regex-backtrack is NPC. So rewording that: * The linked article shows regex+backtrack >= SAT. * Independently we observe that checking an alleged regex+backtrack solution is a polynomial task, therefore regex+backtrack is in NP. * SAT is in NPC, therefore regex+backtrack <= SAT (because regex+backtrack is in NP). * Thus regex+backtrack = SAT (for some definition of "=") So, I think you must have misread something ... I think everything I've written is correct as stands. |
That's the point I missed at first. That's good news, because I was pretty sure perl regex were accidentally Turing complete, I don't know why.