Question

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

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.