0
$\begingroup$

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

$\endgroup$
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$ Aug 7, 2023 at 10:16

2 Answers 2

4
$\begingroup$

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}$).

$\endgroup$
1
$\begingroup$

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}$.

$\endgroup$
2
  • 1
    $\begingroup$ Why do you say that $L_A \not\in \mathsf{P}$? It is currently unknown whether $L_A \in \mathsf{P}$. $\endgroup$
    – Steven
    Aug 6, 2023 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, 2023 at 17:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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