# FO-Logic: Two theories in the same complexity class can always be reduced to each other in polynomial space and time

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

• What do you mean by "two theories in the se complexity class"? What is a "theory"? Did you mean two descision problems? Also, what do you define by "same complexity class"? How do you define a complexity class? Is that an arbitrary set of languages? Nov 28, 2021 at 19:02
• – D.W.
Nov 29, 2021 at 0:31
• – D.W.
Nov 29, 2021 at 0:33
• en.wikipedia.org/wiki/NP-intermediate
– D.W.
Nov 29, 2021 at 0:34
• @nirshahar As this is part of our First-order logic section a theory is just first-order logic with a specified domain of discourse. About the complexity classes I am not sure but I guess that we stick to the known ones or we just create our own ones. But I am not 100% sure about that as I haven't got any additional information.
– Max
Nov 29, 2021 at 7:50