1
$\begingroup$

I am studying complexity theory and I have problem with understanding some concepts about it. Can anyone help me please?

I have some problems with Rice Theorem. It says let $C$ be a class of partially decidable languages, let $L_C= \{<M> | L(M) \in C \}$. Then $L_C$ is decidable iff $C$ is either empty or contain all partially decidable languages.

Regarding this,

In proving undecidability using Rice Theorem, firstly, we provide an example which is not in $L_C$ and another one which is in $L_C$. This is to prove, the language is not trivial which makes sense. However, when we say let $A$ and $B$ be two languages that $L(A)= L(B)$, then both should have property $C$ or none of them have this property. What are we proving here? I mean why we do this?

Secondly, as we know, all finite languages are decidable. On the other hand, we can simply use Rice Theorem to prove that the class of finite languages are undecidable. How is it possible? How does it make sense that each member of a class is decidable, but considering the class, it will be undecidable?

My third question is not about Rice theorem but about concept of decidability itself. By definition, a language $L$ is decidable if there is a TM M that for any input $x$, it always halt and decides whether it accept or reject it. Based on this definition, we can say that all NP problems are decidable by defining a TM that for any input x, accept whenever the answer is a 'yes' and rejects whenever the answer is a 'no'. But, can we also say that decidable languages are in NP class? Because the NP problems are the ones that are verifiable in polynomial time and to me, and this is what a TM is doing for decidable languages. Is it true? If not, what am I getting wrong here?

Any answer to one of these questions would be really helpful and I really appreciate it.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

How does it make sense that each member of a class is decidable, but considering the class, it will be undecidable?

  1. As your third question says, each member of the class is decidable means: if $L$ is in our class, we have a TM deciding it. But can you think of any way to use these TMs to help decide if an arbitrary language is in our class? I can't. Note their inputs are different as well.
  2. Does the opposite also seem confusing: the class of all languages is of course decidable (the decision procedure is just returning "yes" for every program), but it contains many undecidable languages?
  3. This is even a further analogy, but is it confusing that there can be an infinite set of finite sets or a finite set of infinite sets?

that all NP problems are decidable by defining a TM that for any input x, accept whenever the answer is a 'yes' and rejects whenever the answer is a 'no'

But how do you find if the answer is "yes" or "no"? Since the problem is NP, there is a verifying TM but it doesn't just take $x$ as its input, it needs a certificate as well. It's true that all NP problems are decidable, but your argument isn't sufficient.

But, can we also say that decidable languages are in NP class? Because the NP problems are the ones that are verifiable in polynomial time and to me, and this is what a TM is doing for decidable languages.

No, a language is decidable means that a program deciding it exists. But it can take much more than polynomial time.

Improve this answer
$\endgroup$
13
  • 1
    $\begingroup$ @Ali.A How do we get from that to an algorithm deciding whether or not there is a correct solution? That’s the crucial missing step.(“Certificate” is just the official name for what you’re calling a “solution”.) $\endgroup$ Commented Jan 6 at 3:07
  • 1
    $\begingroup$ @Ali.A I think you are confusing the input to the problem with the certificate. Say the problem is whether a graph has a Hamiltonian cycle. A verifier has two inputs, the problem input (a graph) and a certificate (a purported Hamiltonian cycle). The verifier, given a graph and a purported Hamiltonian cycle, verifies whether it is indeed a valid Hamiltonian cycle in this graph. We give the verifier the graph and a bunch of junk, and it says "no". Does that mean the decider should say "no", i.e. that there is no Hamiltonian cycle? $\endgroup$ Commented Jan 6 at 7:24
  • 2
    $\begingroup$ @Ali.A Worst case, you just brute force search through every possible value of the certificate and ask the verifier about each. If you find one that verifies, decide yes. If you get through all of them and it doesn't verify any, decide no. $\endgroup$ Commented Jan 6 at 14:41
  • 1
    $\begingroup$ @Ali.A (Note though this is using crucially that it is polynomial time verifiable not just verifiable, since in this former case we have an upper bound on the size of a certificate so only a finite number to check. It should make sense that this is the case for Hamiltonian path since there's only $|V-1|!$ cycle orders for the vertices we could propose. Verifiable (without any resource bounds) does not imply decidable since there are infinitely many certificates to check... it is equivalent to being semi-decidable.) $\endgroup$ Commented Jan 6 at 20:02
  • 1
    $\begingroup$ @Ali.A If there's some upper bound on the number of certificates that need to be checked that's computable from the input then it is decidable... yes that's a theorem. And this is the case for all NP problems. There is some polynomial $p(n)$ in the input size that bounds the time the verifier can take, so the verifier will only be able to look at the first $p(n)$ bits of the certificate, so you only need to check certificates of length $\le p(n)$ for inputs of size $n.$ $\endgroup$ Commented Jan 6 at 20:17

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.