3CNF SAT

Concept: - In 3CNF SAT, you have at least 3 clauses, and in clauses, you will have almost 3 literals or constants

Such as (X+Y+Z) (X+Y+Z) (X+Y+Z)
You can define as (XvYvZ) ᶺ (XvYvZ) ᶺ (XvYvZ)
V=OR operator
^ =AND operator

These all the following points need to be considered in 3CNF SAT.

To prove: -

1. Concept of 3CNF SAT
2. SAT≤ρ 3CNF SAT
3. 3CNF≤ρ SAT
4. 3CNF ϵ NPC

1. CONCEPT: - In 3CNF SAT, you have at least 3 clauses, and in clauses, you will have almost 3 literals or constants.
2. SAT ≤ρ 3CNF SAT:- In which firstly you need to convert a Boolean function created in SAT into 3CNF either in POS or SOP form within the polynomial time
        F=X+YZ
           = (X+Y) (X+Z)
          = (X+Y+ZZ') (X+YY'+Z)
          = (X+Y+Z) (X+Y+Z') (X+Y+Z) (X+Y'+Z)
          = (X+Y+Z) (X+Y+Z') (X+Y'+Z)
3. 3CNF ≤p SAT: - From the Boolean Function having three literals we can reduce the whole function into a shorter one.
        F= (X+Y+Z) (X+Y+Z') (X+Y'+Z)
          = (X+Y+Z) (X+Y+Z') (X+Y+Z) (X+Y'+Z)
          = (X+Y+ZZ') (X+YY'+Z)
          = (X+Y) (X+Z)
          = X+YZ
4. 3CNF ϵ NPC: - As you know very well, you can get the 3CNF through SAT and SAT through CIRCUIT SAT that comes from NP.

Proof of NPC:-

1. It shows that you can easily convert a Boolean function of SAT into 3CNF SAT and satisfied the concept of 3CNF SAT also within polynomial time through Reduction concept.
2. If you want to verify the output in 3CNF SAT then perform the Reduction and convert into SAT and CIRCUIT also to check the output

If you can achieve these two points that means 3CNF SAT also in NPC