I have a solution that has a linear time complexity to the number of clauses in the CNF formula, which is O(c^2 X n), such that n is the number of different variables in the CNF formula, will this solution be considered as a linear solution to K-CNF or not? Since the number of clauses may be c = 2^n What is the real variable that the algorithm should have it linear in order to solve K-CNF? Can it be C? or it should be n? or what?
I am not understanding the CNF complexity problem correctly
In complexity theory, the runtime of an algorithm is typically measured as a function of the length of the input in bits. So, for example, if your algorithm’s runtime is linear in the number of clauses, since the number of clauses is a linear function of the input size, then your algorithm would be a linear-time solution to k-SAT.
A linear-time algorithm for k-SAT would be a major breakthrough in theoretical CS. Have you tested it extensively? There are (used to be?) yearly competitions for SAT solvers to see just how well they’d perform on huge inputs. You might want to download some test cases from there if you haven’t already done so to validate your algorithm on difficult cases assembled over the last fifty or so years.