The reduction from 3SAT to SUBSET-SUM includes building a table as follows: enter image description here

Where base 10 representation is used for the rows in the table. I would like to know if the reduction will still be correct if we replace the base 10 representation with the following bases: 2, 3 or 6?

  • 1
    $\begingroup$ Please edit your first post instead of creating a new question… $\endgroup$ – Nathaniel May 6 at 20:25
  • $\begingroup$ 1. Please give context. A single picture is not enough to understand the specifics of the reduction. The more effort you put into making your question useful to others and easy for others to understand, the more likely that you'll get a good answer. Make sure to properly attribute any images or text that you copy from elsewhere. $\endgroup$ – D.W. May 6 at 22:38
  • $\begingroup$ 2. What are your thoughts? The standard reduction comes with a proof of correctness. I suggest that you write out your proposed revision, try to prove it correct following the same approach, and see if the proof works out. That is work you should do before asking - then if you get stuck and have a specific question about some aspect of that, show us what progress you've made and articulate that specific question. $\endgroup$ – D.W. May 6 at 22:38

This was an examination paper question for Computability and Complexity, as the deadline has now passed, I am able to answer:

The basic answer to this is that it is quite literally, base 2, 3 and base 6. If my answer itself was correct, you can see in the table we must have the second half of the answer to contain only "3" values, that is to say, 33333,...33333.

It quite literally does mean "base x" here, in that base 10 (our usual numbering system base) would give us the ranges of {0,1,2,3,4,5,6,7,8,9}.

As such, base 10 is appropriate, as its set contains 3.

Base 2 and 3 will give us {0,1} and {0,1,2} respectively. As such they cannot represent "3" and would not work in the general answer.

Base 6 however, gives us the set {0,1,2,3,4,5} which as it contains 3, gives us a base capable of representing the table.

As such, base 4 is the minimum base required to represent the table as this is the lowest value that includes 3. ({0,1,2,3})

I hope you figured this out in the exam, a useful link for this would have been: https://math.stackexchange.com/questions/2630604/reduction-3sat-to-subset-sum

Which better explains the reasoning, I have only tried to explain the exact answer.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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