> Was wondering if anyone else noticed this. I thought in class we
> defined polynomial time reductions from decision problem to decision
> problem. Clearly Q6 in both the sample exams, the questions asks for
> a Turing polytime reduction from a non decision problem to a decision
> problem - anyone know what they exactly mean here?
>
> (From what I think they could mean, the Subset Sum to SSP should be
> almost trivial and somehow would be worth 8 marks?)
>
> Thanks

> Carmen Bruni wrote:

>> Was wondering if anyone else noticed this.  I thought in class we
>> defined polynomial time reductions from decision problem to decision
>> problem.  Clearly Q6 in both the sample exams, the questions asks for
>> a Turing polytime reduction from a non decision problem to a decision
>> problem - anyone know what they exactly mean here?

>

>> (From what I think they could mean, the Subset Sum to SSP should be
>> almost trivial and somehow would be worth 8 marks?)

>

>> Thanks

>
> We also defined polynomial time reductions for non-decision problem's to
> decision problems. A good example is from travelling salesman to
> TSP-Decision. Here we did a binary search to get a reduction that is
> O(log(W)), and...

> On Aug 6, 4:08 pm, Thomas Dimson gmail.com> wrote:

>> Carmen Bruni wrote:

>>> Was wondering if anyone else noticed this. I thought in class we
>>> defined polynomial time reductions from decision problem to decision
>>> problem. Clearly Q6 in both the sample exams, the questions asks for
>>> a Turing polytime reduction from a non decision problem to a decision
>>> problem - anyone know what they exactly mean here?
>>> (From what I think they could mean, the Subset Sum to SSP should be
>>> almost trivial and somehow would be worth 8 marks?)
>>> Thanks

>> We also defined polynomial time reductions for non-decision problem's to
>> decision problems. A good example is from travelling salesman to
>> TSP-Decision. Here we did a binary search to get a reduction that is
>> O(log(W)), and since W is exponential in # bits, the reduction is O(n).

>
> Okay that I agree with - so you interpretted it like I did - Show we
> can solve the first problem in polynomial time if and only if we can
> solve the second problem in polynomial time. Since that is what we
> did with the TSP problem I imagine you're applying the same reasoning ...