MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I read somewhere that 3SAT can be used to solve Integer Factorization.

If that is true, could someone teach me a simple example of generating the 3SAT by using a small number? Let's say you are given the number 6, then the factors are 2 and 3.

share|cite|improve this question
up vote 1 down vote accepted answers this question directly.

share|cite|improve this answer

This is not a research level question, but it follows immediately from the NP-hardness of 3SAT. The old book "Computers and Intractability" by Garey and Johnson used to be (i.e. there might be something better now) a good place to learn this topic. It's not something that can be explained in a few paragraphs. (the computer science stackexchange) is a better place for this type of question if you need further help.

share|cite|improve this answer
thanks. i'm posting it to stackexchange.. someone help me close this qn. – Jane May 2 '13 at 6:10

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.