Complications of a language that reaches a state of reject

Question

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.

Answer 1

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.