[Solved]: Semi-decidable problems with linear bound

Problem Detail: 

Take a semi-decidable problem and an algorithm that finds the positive answer in finite time. The run-time of the algorithm, restricted to inputs with a positive answer, cannot be bounded by a computable function. (Otherwise we'd know how long to wait for a positive answer. If the algorithm runs longer than that we know that the answer is no and the problem would be solvable.)

My question is now: Can such an algorithm still have a, say, a run-time bound linear (polynomial, constant,...) in the input size, but with an uncomputable constant? Or would that still allow me to decide the problem? Are there example?

Asked By : Joachim Breitner

Answered By : Jan Johannsen

For your sketched decision algorithm to work, it is sufficient that the run-time is majorized by a computable function. Every linear function $n \mapsto c\cdot n$ even for non-computable c is majorized by a computable function, viz., $n \mapsto \lceil c \rceil \cdot n$. Thus the answer to the question is no: a semi-decision procedure for an undecidable problem cannot have linear run-time (or a run-time majorized by any computable function.)

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/2425

3.2K people like this

 Download Related Notes/Documents