# How to prove that the subset of a language L that is in P is also in P?

Given that $$L∈\textrm{P}$$, how do we show that an arbitrary subset $$L_{A}$$ of $$L$$ is also in P?

• A general hint I encountered here years ago: whenever asked how to do something for arbitrary languages $L$, first consider the cases $L = \emptyset$ and $L = \Sigma^*$. Aug 7, 2023 at 10:16

You cannot show that, since the claim is false. Let $$L = \Sigma^*$$ and let $$L_A \subset \Sigma^*$$ be the language of the halting problem. Clearly $$L \in \mathsf{P}$$ (a Turing machine that decides $$L$$ is the one that ignores its input and immediately accepts). However $$L_A$$ is well-known to be undecidable (and hence not in $$\mathsf{P}$$).
By $$\textrm{P}$$ do you mean the languages that are decidable in polynomial time? If so, I am pretty sure this isn't true. For example, let $$L$$ be the language of graphs that are 2-edge-connected, and $$L_A$$ the language of graphs that contain Hamiltonian cycles. Then $$L \in \textrm{P}$$ and $$L_A \subseteq L$$ but $$L_A \not\in \textrm{P}$$, unless $$\textrm{P} = \textrm{NP}$$.
• Why do you say that $L_A \not\in \mathsf{P}$? It is currently unknown whether $L_A \in \mathsf{P}$. Aug 6, 2023 at 17:25
• Yes, you are right. I meant that it is believed that $L_A \not\in \textrm{P}$ and if the original question's claim were true it would show that $\textrm{P} = \textrm{NP}$. Your answer is a more concrete refutation. Aug 6, 2023 at 17:30