Why is 3SAT harder than 2SATSolutionFirst to understand the

Why is 3-SAT harder than 2-SAT?

Solution

First to understand the difference between 3-SAT and 2-SAT, we must understand the the terms Decision problem, P and NP-complete and then only we move further on this point.
Decision making
Decision making In computability theory and computational complexity theory, a decision problem is a question in some formal system that can be posed as a yes-no question, dependant on the input values. Decision problems typically appear in mathematical questions of decidability, that is, the question of the existence of an effective method to determine the existence of some object or its membership in a set.
For example, the problem \"given two numbers a and b, does a evenly divide b?\" is a decision problem. The answer can be either \'yes\' or \'no\', and depends upon the values of a and b.
A method for solving a decision problem, given in the form of an algorithm, is called a decision procedure for that problem.

Now decision problems can be
1. polynomial time (polynomial time is a synonym for \"tractable\", \"feasible\", \"efficient\", or \"fast\".)
2. non determistic polynomial time theory is technique to solve the more complex decision problems.In a deterministic Turing machine, the set of rules prescribes at most one action to be performed for any given situation. By contrast, a non-deterministic Turing machine (NTM) may have a set of rules that prescribes more than one action for a given situation.
For example, a non-deterministic Turing machine may have both \"If you are in state 2 and you see an \'A\', change it to a \'B\' and move left\" and \"If you are in state 2 and you see an \'A\', change it to a \'C\' and move right\" in its rule set.
3. Np-Complete which covers both p and NP type problems

Now move to actual questiuon that why 3-sat and 2-sat

2-SAT is in P and in NP.if any problem in P (or in NP) is not NP complete, then P!=NP. so if 2-SAT is not NP-complete, then P!=NP.
if P!=NP, then NP-complete problems are not in P.so if 2-SAT is not NP-complete, then P!=NP and 3-SAT (being NP-complete) is not in P
equivalently (easier):

3-SAT is NP-complete.if an NP-complete problem is in P, then P=NP.
if P=NP, then every problem in P is NP-complete.2-SAT is in P (and in NP).so if 3-SAT is in P, then P=NP and every P (and NP) problem is NP-complete, including 2-SAT.

that\'s the reason 3-SAT is harder then 2-SAT.