This is for sure not a java questoin but I have really no idea where to post it else: Given is a yes/no problem P for the instance n. There is an existing reduction from P to Q with the timecomplexity O(n^2). Q is also NP-complete.
Now asume that the problem Q can be solved in O(m^2 log(m)) with the input parameter m. Does this implicate, that every instance of sat can be solved in polynomical time?
I'm going to assume that by "sat" you mean the Boolean Satisfiability Problem. If you're going to use acronyms, please write them in capital letters. The Boolean Satisfiability Problem is also known as SAT.
By definition, if Q is NP-complete and can be solved in polynomial time, then every NP-complete problem can be solved in polynomial time, including SAT.
Good luck finding an algorithm that solves Q in polynomial time.
posted 4 weeks ago
Thanks for your help. Yes I ment the Boolean Satisfiability Problem.