15 votes 15 votes The problem $\text{3-SAT}$ and $\text{2-SAT}$ are both in $\text{P}$ both $\text{NP}$ complete $\text{NP}$-complete and in $\text{P}$ respectively undecidable and $\text{NP}$ complete respectively Algorithms gatecse-2004 algorithms p-np-npc-nph easy isro2017 out-of-gate-syllabus + – Kathleen asked Sep 18, 2014 edited Jun 13, 2018 by Milicevic3306 Kathleen 11.7k views answer comment Share Follow See 1 comment See all 1 1 comment reply Barney Ross commented Jul 2, 2018 reply Follow Share Is this part of syllabus now? 1 votes 1 votes Please log in or register to add a comment.
2 votes 2 votes 3-SAT and 2-SAT are special cases of k-satisfiability (k-SAT) or simply satisfiability (SAT) when each clause contains exactly k = 3 and k = 2 literals respectively. 2-SAT is P while 3-SAT is NP-Complete. http://suraj.lums.edu.pk/~cs514s05/data/2SAT.pdf pankaj_vir answered Mar 12, 2018 pankaj_vir comment Share Follow See all 0 reply Please log in or register to add a comment.
–1 votes –1 votes 3 sat np and 2 sat p problem naveenagrahari answered Jul 10, 2015 naveenagrahari comment Share Follow See all 0 reply Please log in or register to add a comment.
–1 votes –1 votes Option C is correct. Purvi Agrawal answered May 7, 2017 Purvi Agrawal comment Share Follow See all 2 Comments See all 2 2 Comments reply Ishan Jawa commented May 7, 2017 reply Follow Share 2 sat is solvable in polynomial time whereas 3 sat is in np 0 votes 0 votes Purvi Agrawal commented May 7, 2017 reply Follow Share 3 Sat in NP-C 0 votes 0 votes Please log in or register to add a comment.