0
$\begingroup$

I have to prove that if L <=p L1 intersection L2, where L1 and L2 are described as above, L belongs to NP.

I thought about the definitions of P and NP and built a DTM D that decides L2 and a NTM N that decides L1. Then I tried to build a NTM NN that accepts when both D and N accept on some input w.

Now,did I really prove that intersection between L1 and L2 is in NP by constructing NTM NN? Thx in advance

Improve this question
$\endgroup$
2
  • $\begingroup$ Welcome to Computer Science! Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. $\endgroup$
    – Raphael
    Commented May 25, 2016 at 13:35
  • $\begingroup$ Idea is correct, however you have to explicitly create a single turing machine to do the task. $\endgroup$
    – Sarvottamananda
    Commented May 25, 2016 at 13:54

1 Answer 1

Reset to default
1
$\begingroup$

You can prove something more, intersection of two NP languages is also in NP.

Suppose you have polynomial time non-deterministic turing machines $M_1$ for $L_1$ and $M_2$ for $L_2$. We can modify $M_1$ as follows: Whenever any non-deterministic thread of $M_1$ accepts input string, say $w$, we run $M_2$ on $w$, if $M_2$ then accepts $w$, accept the input, otherwise reject.

The resulting machine is polynomial time non-deterministic.

Improve this answer
$\endgroup$

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.