Alex12

Hello. I am looking for someone who can give the online help for me on my TCS exam on Saturday (14/04) the topics: NP-completeness of 3SAT, 1-3-SAT, NAE-3SAT, Clique, Subsetsum, 0-1 integer programming NP-Completeness of HAMPATH. Classes PSPACE, NPSPACE, EXPSPACE. Oracle computation and oracles for which P^A=NP^A and for which P^A != NP^A.

Hello all. Recently I have read the article: 'A. Agrawa, D. Lokshtanov, S. Saurabh and M. Zehavi. Split Contraction: The Untold Story'. I am interested in the theorem from the article. The theorem statement can be stated as: «SRBPC parameterized by the number of parts in R is W[1]-hard». I did not understand what is Split Contraction, SRBPC, Perfect Code and W[1]-hard. Could you please explain it easier for me? And I need explanation the proof of the theorem. As I understood, the theorem proofs through some Lemmas. And I ask you to explain for me these lemmas easier. Thanks.