Given that $L∈\textrm{P}$, how do we show that an arbitrary subset $L_{A}$ of $L$ is also in P?
1
-
$\begingroup$ 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^*$. $\endgroup$– reinierpostAug 7 at 10:16
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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}$).
$\begingroup$
$\endgroup$
2
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}$.
-
1$\begingroup$ Why do you say that $L_A \not\in \mathsf{P}$? It is currently unknown whether $L_A \in \mathsf{P}$. $\endgroup$– StevenAug 6 at 17:25
-
$\begingroup$ 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. $\endgroup$ Aug 6 at 17:30