Question

Let language L consist of simple, undirected graphs that contain at least one cycle. Prove that L...

Let language L consist of simple, undirected graphs that contain at least one cycle. Prove that L ∈ NP.

0 0
Add a comment Improve this question Transcribed image text
Answer #1

The goal of this question is to show that if P=NP then for every language L∈NP via a polynomial time verifier V, there is a polynomial time algorithm that given x∈L finds a certificate satisfying V.

Let V be a polynomial time verifier over {0,1} such that all strings accepted are of the form 〈x,c〉 where x,c∈{0,1}∗.

Let L⊆{0,1}∗ be a language and let d be a positive integer such that for every x∈L, there is a string c of length |x|d such that V accepts 〈x,c〉 and for every x∉L, there is no string c such that V accepts 〈x,c〉.

Let L′={〈x,c1〉 | x,c1∈{0,1}∗ and for some c2∈{0,1}∗, V accepts 〈x,c1c2〉 and |c1c2|=|x|d }

Prove that L′∈NP.

My approach would be to show that L′≤pL by some reduction function, however, I am not sure of this.

Add a comment
Know the answer?
Add Answer to:
Let language L consist of simple, undirected graphs that contain at least one cycle. Prove that L...
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for? Ask your own homework help question. Our experts will answer your question WITHIN MINUTES for Free.
Similar Homework Help Questions
ADVERTISEMENT
Free Homework Help App
Download From Google Play
Scan Your Homework
to Get Instant Free Answers
Need Online Homework Help?
Ask a Question
Get Answers For Free
Most questions answered within 3 hours.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT