programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Devaka Cooray
• Knute Snortum
• Paul Clapham
• Tim Cooke
Sheriffs:
• Liutauras Vilda
• Jeanne Boyarsky
• Bear Bibeault
Saloon Keepers:
• Tim Moores
• Stephan van Hulst
• Ron McLeod
• Piet Souris
• Frits Walraven
Bartenders:
• Ganesh Patekar
• Tim Holloway
• salvin francis

# How to identify if every instance of a sat can be solved in polynomical time

Greenhorn
Posts: 15
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?

Saloon Keeper
Posts: 10218
216
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.

Hans Peterson
Greenhorn
Posts: 15
Thanks for your help. Yes I ment the Boolean Satisfiability Problem.

 Did you see how Paul cut 87% off of his electric heat bill with 82 watts of micro heaters?