• Post Reply Bookmark Topic Watch Topic
  • New Topic
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  RSS feed

 
Greenhorn
Posts: 15
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks for your help. Yes I ment the Boolean Satisfiability Problem.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!