Briefly describe the idea of the polynomial time reduction. Explain how to use it to
prove a problem is NP-complete.
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.
在计算复杂性理论中，多项式时间归约是指假设已有解决一个问题的子程序，利用它在多项式时间内（不考虑子程序运行所用时间）解决另一个问题的归约方法
在计算复杂性理论中，多项式时间约简是一种使用一个问题解决另一个问题的方法。一个表明，如果存在解决第二个问题的假设子例程，则可以通过将其转换或简化为第二个问题的输入并调用子例程一次或多次来解决第一个问题。如果将第一个问题转换为第二个问题所需的时间和调用子例程的次数都是多项式的，那么第一个问题是多项式时间可约化为第二个问题。
多项式时间约简证明，第一个问题并不比第二个问题困难，因为只要第二个问题存在有效的算法，第一个问题也存在一个算法。通过对置，如果第一个问题不存在有效的算法，那么第二个问题也不存在。多项式时间约简在复杂性理论中经常用于定义复杂性类和这些类的完全问题。