I am currently studying CS and came across a question in my lecture. Question: Two theories in the same complexity class can always be reduced to each other in polynomial space and time. This is part of our First-order logic lecture.

I am quite sure that this is possible if both problems are decidable and that the polynomial space and time constraint is fine. But I am not sure how the behavior is when one theory is decidable and the other isn't. So basically T1 is decidable and T2 isn't then we might fail to map all instances from T2 to T1 as there could be an instance I, which would result in an infinite loop in T2 so basically (no answer) T2(I) = infinite where on the other hand T1 will always return an answer.

So basically decidable -> undecidable works ( Lets say M decides something then we could create M' which performs like M but switches into an infinite loop when M rejects, so this direction should work) but undecidable -> decidable is unclear to me, because I don't see how we would generate the infinite loop state inside T1 as by definition its decidable and always returns an answer. Also there might be some complexity-classes where the space or time constrain for the reduction would fail but I have no idea about this as we have just talked about NP, P and haven't got into EXPTime etc.

Also how would you understand the question ? As it is phrased we should be able to reduce T1->T2 and T2->T1, so in both directions. But based on my current knowledge there should be at least one direction but not both. Or how would you understand each other ? I am not a native English speaker so I am not always 100% if I got the question correctly.

Based on my opinion the answer to the question should be no.

Regards Max



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.