Polynomial time: Accepting and Decision Algorithms [closed]

Question

Closed. This question does not meet Stack Overflow guidelines. It is not currently accepting answers.

---

This question does not appear to be about programming within the scope defined in the help center.

Closed 8 years ago.

Improve this question

I don't seem to be able to distinguish Accepting and Decision Algorithms, even though I feel like I do understand the concept. I am currently reading "Introduction to Algorithms" (Cormen), and have a problem following chapter NP-Completeness, as it states that

"For other Problems, such as Turing's Halting Problem, there exists an accepting algorithm, but no decision algorithm exists".

This does make sense up to this point to me, but then we go further and say that

"P= {L from {0,1}*: there exists an algorithm A that decides L in polynomial time}

And we want to prove that P also is

P={L:L is accepted by a polynomial time algorithm}, starting with

"Because the class of languages decided by a polynomial-time algorithms, we need only show that if L is accepted by a polynomial-time algorithm, it is decided by a polynomial-time algorithm.".

Then we go ahead and construct a simulation of an accepting algorithm that additionally inspects the behavior of the accepting algorithm and outputs 1 if the former Algorithm accepted the input and 0 if not.

But if we can construct such an algorithm, how is it possible that the Halting Problem has an accepting, but not a decision algorithm?

Answer 1

The difference has to do with the upper bound on the runtime. When considering a polynomial-time algorithm, if you have a polynomial-time acceptor, you can turn it into a polynomial-time decider as follows:

• Run the algorithm for the polynomial amount of time it would take to accept in the worst-case.
• If it accepts in this time, great! Accept.
• If it doesn't accept in this time, it's never going to accept. Reject.

Therefore, the accepter can be turned into a decider.

Now, think about the same thing for the halting problem:

• Run the algorithm as long as it would take to accept in the worst-case.
• If it accepts in this time, great! Accept.
• If it doesn't accept in this time, it's never going to accept. Reject.

The problem here is that there isn't some fixed amount of time in which the algorithm will accept - programs can run arbitrarily long before accepting, so there's no way to say "run it until it would have already accepted," since there's no computational process that can figure out what time this is.

Interestingly, this connects to the Busy Beaver function. A busy-beaver of size n is, intuitively, a program of length n that always halts, but takes the longest possible time to halt out of all programs of size n. For a particular input w, the busy beaver number for w of order n is the number of steps it will take the busy beaver program of size n to halt on the input w. This number is mathematically well-defined, but it can't be computed by any computer program or otherwise you could use it to make the above algorithm work correctly.

Hope this helps!