<p>Is there any sensible complexity measure that makes sense to compare the &quot;hardness&quot; of undecidable semi-decidable problems? Time and space are of course not suitable, because they cannot be bounded in any way if the problem is undecidable.</p>
<p>But is there any other notion that makes sense to say that one problem is &quot;harder&quot; than another even though both are semi-decidable?</p>

CC BY-SA 4.0
2023-09-13T19:14:11.633Z
Fix your favourite notion of [reduction](https://en.wikipedia.org/wiki/Reduction_(computability_theory)), and say that A is harder than B if B reduces to A but A does not reduce to B.
Emil Jeřábek
CC BY-SA 4.0
2023-09-13T20:06:30.467Z
Are you so sure time & space aren't suitable? You could still talk about the time, space, etc complexity *on inputs where the machine halts*.
Joshua Grochow
CC BY-SA 4.0
2023-09-13T20:43:18.337Z
If I found an upper bound on the time took on terminating instances, couldn’t I just wait for that time and answer on non-terminating instances as well?
Nicola Gigante
CC BY-SA 4.0
2023-09-13T21:46:49.090Z
Only if the upper bound is a computable function.
Joshua Grochow
CC BY-SA 4.0
2023-09-14T17:59:07.767Z
Interesting. Is there an example of undecidable problem where a semi-decision procedure has a non-computable upper bound on the running time for accepted instances?
Nicola Gigante
CC BY-SA 4.0
2023-09-15T14:10:50.173Z
Your same argument from above implies that's true for any non-computable, semi-computable problem. (Eg the Halting problem)
Joshua Grochow
<cc.complexity-theory><computability>
Complexity measures for semi-decidable problems
Nicola Gigante
# Complexity measures for semi-decidable problems

(Asked by: username_0 on 2023-09-13)

Is there any sensible complexity measure that makes sense to compare the "hardness" of undecidable semi-decidable problems? Time and space are of course not suitable, because they cannot be bounded in any way if the problem is undecidable.

But is there any other notion that makes sense to say that one problem is "harder" than another even though both are semi-decidable?

**Tags:** cc.complexity-theory, computability
> **Comments:**
> **username_1**: Fix your favourite notion of [reduction](https://en.wikipedia.org/wiki/Reduction_(computability_theory)), and say that A is harder than B if B reduces to A but A does not reduce to B.  
> **username_2**: Are you so sure time & space aren't suitable? You could still talk about the time, space, etc complexity *on inputs where the machine halts*.  
> **username_0**: If I found an upper bound on the time took on terminating instances, couldn’t I just wait for that time and answer on non-terminating instances as well?  
> **username_2**: Only if the upper bound is a computable function.  
> **username_0**: Interesting. Is there an example of undecidable problem where a semi-decision procedure has a non-computable upper bound on the running time for accepted instances?  
> **username_2**: Your same argument from above implies that's true for any non-computable, semi-computable problem. (Eg the Halting problem)  

---

## 0 answers

