Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question

2 Answers 2

up vote 1 down vote accepted

http://cstheory.stackexchange.com/questions/6755/fast-reduction-from-rsa-to-sat answers this question directly.

share|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. cs.stackexchange.com (the computer science stackexchange) is a better place for this type of question if you need further help.

share|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

 
discard

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.