| > I'm assuming you are working on solving some NP-hard problem? Yes, my choice of the problem is 2XSAT, which is a SAT class whose instances have clauses from 2-SAT and XORSAT. I proved (and I think that's where it becomes novel) that this class is NP-complete. This leads me to believe there is a clever generalization of polynomial algorithms for 2-SAT and XORSAT, and that's the subject of my interest. The trouble is, algorithms for 2-SAT and XORSAT are wildly different. My first attempt to unify them, half a year ago, has failed. Since then I have made a lot of progress on the theory; now I have another candidate algorithm which generalizes them, and I am about to test it. > Yes, that's a good approach! I know, but it gets even better. I roughly follow what Krom did with 2-SAT in 1967. And it turns out, even if your attempt at polynomial algorithm turns out to be incorrect, the character of the exponential blow-up gives you at least some hint of what you need to fix. > I'd be happy to take a look. I wish I had written more on it, but the research got priority. For two months now, I am sitting on blogpost draft that outlines 2/3 of my strategy, as well as half of a proper paper; I was waiting if I can somehow conclude with a candidate algorithm, but I don't really have yet that written down in a formal way (it's new so some understanding needs to happen). I'll probably publish the blogpost as it is, and the actual algorithm (if the test implementation works out reasonably well) later as another blogpost. If you're still interested, I will send you an email when I publish the first part, probably this weekend, and you can tell me what you think. |
My academic background is more on linear optimisation (and integer and combinatorial optimisation), but looking more into the various flavours of SAT would also be interesting.