简要地描述多项式时间约简的思想

Question

1. Briefly describe the idea of the polynomial time reduction. Explain how to use it to
   prove a problem is NP-complete.

2. 4-SAT Problem: for a Boolean formula in CNF in which each clause has exactly 4
   literals, determine if there is an assignment of Boolean value to its variables so that
   the formula evaluates to true? (i.e., the formula is satisfiable). Prove 4-SAT Problem
   is NP-Complete.

Answer 1

在计算复杂性理论中，多项式时间归约是指假设已有解决一个问题的子程序，利用它在多项式时间内（不考虑子程序运行所用时间）解决另一个问题的归约方法