Is there a standard way to determine a complexity of the specified SAT problem? I'm researching algebraic cryptanalysis and came to solving multivariate quadratic equation systems using CryptoMiniSat. However it would nice to evaluate a complexity of the full cipher equation system. Does it only depend on the number of polynomials and variables? And is there a way to estimate the time needed for solving the equation system and what parameters do I need to know to find that out?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
No, there is not.
Your question is not well-posed. You have not specified whether you want worst-case complexity or average-case complexity, and over what class of SAT instances. The answer will depend heavily upon those details.
If you want to know what is the world record for an algorithm for 3SAT, measured by its worst-case complexity over all possible 3SAT instances, that's a question to ask on http://cs.stackexchange.com/ or http://cstheory.stackexchange.com/ . See, e.g., Best Upper Bounds on SAT and Measuring the difficulty of SAT instances. But don't expect these theoretical results to necessarily have any relationship to the performance of SAT solvers in practice.