0
$\begingroup$

I have a question that is not clear to me, and I have not been able to answer it from a test I had.

This is the question

Let's look at the language $L_\mathrm{reject} = ${ $\left \langle M,w \right \rangle$ | When $M$ is activated on the input $w$, the machine $M$ reach to reject state }

We will mark our input length: $|\left \langle M,w \right \rangle| = n$. Determine which of the claims is correct:

  1. The language is not in $\mathsf{NPH}$ or $\mathsf{CoNPH}$.
  2. The language is in $\mathsf{NP}$ but not in $\mathsf{NPC}$.
  3. The language is in $\mathsf{P}$
  4. The language belongs to $\mathsf{NPH}$.
  5. None of the above claims are true.

I think the language should be CoNPH, or CoNPC because the language is in a reject state every time, and this is what is tested in CoNPC if it is possible to build an algorithm that returns a failure.

  1. I think this is not true, in my opinion, the language should be in CoNPC because the machine always gets into a reject state, which is always a failure.

  2. I do not think it is in NP, because it is not possible to write a non-deterministic algorithm that will say yes

  3. If it's not in NP then surely it's not in P

  4. I think the language belongs to CoNPH, because there is a machine that leads to a reject state, so there is a guessing algorithm, which checks when the language is not accepted - that it is related to CoNPH and not NPH.

  5. I will probably choose this one because I could not find an answer that leads to CoNPC or CoNPH

I can not understand, what it means to have a machine $M$ that gets a word $w$, and then straight goes to reject mode. What does it say about the language it belongs to.

$\endgroup$
1
$\begingroup$

Saying that a "language reaches the state of reject" is meaningless. Languages don't have states. Turing machines and automatons do.

That said, your language is undecidable. Given $\langle M,w \rangle$ you can compute the pair $\langle M',w \rangle$ where $M'$ behaves exactly as $M$ except for the following: every transition that halts the machine and accepts is replaced with a transition that halts the machine and rejects.

Then $\langle M', w \rangle \in L_{\text{reject}}$ if and only if $M$ halts on input $w$. Therefore if $L_{\text{reject}}$ were decidable so would be the halting problem.

As a consequence $L_{\text{reject}}$ is not in $NP$ nor in Co-$NP$ (which only contain decidable problems). This means that 2 is false, and 3 is false (since $P \subseteq NP$).

We can actually build a Karp reduction $f(\cdot)$ from a NP-Hard problem to $L_{\text{reject}}$. Consider for example an instance $\phi$ of $3$-SAT. Construct a Turing Machine $T$ that expects (a suitable encoding of) $w$ of $\phi$ as input and then tries all possible variable assignments. If a satisfying assignment is found then $T$ rejects. Otherwise $T$ enters in an infinite loop. Choose $f(\phi) = \langle T, w \rangle$ and notice that $f$ can be computed in polynomial-time w.r.t. the encoding of $\phi$ (in particular $T$ can be fixed once for all). Then $\phi \in 3\text{-SAT} \iff f(\phi) \in L_{\text{reject}}$. This shows that $L_{\text{reject}}$ is NP-hard, 4 is true, 1 is false, and 5 is false.

$\endgroup$
4
  • $\begingroup$ Thanks for the help, 2 things are not clear to me: why do you actually need $ M' $, why did you need to change $ M $? I do not see how this affects the solution. And why $NPH ⊂ NP$ it should not be the opposite? after all NPH is a harder class than NP, and NP is contained in NPH , $NP ⊂ NPH$ $\endgroup$ Jul 22 at 18:01
  • $\begingroup$ Please see the edited answer. I need to modify $M$ to handle the case in which $M$ halts and accepts on input $w$. When that happens $\langle M, w \rangle$ is a "yes" instance of the halting problem but a "no" instance of $L_{\text{reject}}$. However $\langle M, w \rangle$ is a "yes" instance of the halting problem iff $\langle M', w \rangle$ is a "yes" instance of $L_{\text{reject}}$. $\endgroup$
    – Steven
    Jul 22 at 18:12
  • $\begingroup$ Thanks, how can I do reduction from 3 sat to $L_reject$, if $L_reject$ can get into an infinite loop, why is it not a halting problem? halting problem is in the RE class? $\endgroup$ Jul 22 at 19:03
  • $\begingroup$ The only requirement for a Karp reducution $f$ from $A$ to $B$ is being computable in polynomial time and satisfying $x\in A\iff f(x)\in B$, so that's a valid Karp reduction. Although it's a bit weird to reduce to an undecidable problem, formally you can do it. $L_{\text{reject}}$ is not the language of the halting problem because the answer to an instance of the halting problem is "yes" iff the input Turing machine halts (you don't care whether it accepts or rejects). In $L_{\text{reject}}$ it must reject. However, they are related as my answer shows. Yes, the halting problem is in RE. $\endgroup$
    – Steven
    Jul 22 at 19:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.