Non-deterministic Algorithms (非确定性算法)

A nondeterminstic algorithm consists of

phase 1: guessing 猜测

phase 2: checking 验证

If the checking stage of a nondeterministic

algorithm is of polynomial time-complexity,

then this algorithm is called an NP

(nondeterministic polynomial) algorithm.

NP : the class of decision problem which can

be solved by a non-deterministic polynomial algorithm.

P: the class of problems which can be solved

by a deterministic polynomial algorithm.

NP-hard: the class of problems to which every

NP problem reduces.

NP-complete (NPC): the class of problems

which are NP-hard and belong to NP.

Reduction（问题规约）

Decision problems（判定问题与优化问题）

The solution is simply “Yes” or “No”.

Optimization problems are more difficult than its decision version. 优化问题比判定问题更难

e.g. the traveling salesperson problem 旅行商问题

1.Optimization version: Find the shortest tour

2.Decision version:

Is there a tour whose total length is less than or equal to a constant c

satisfiability problem （可满足性问题）

The satisfiability problem

The logical formula : 判断命题公式的真假

x 1 v x 2 v x 3

& – x 1

& – x 2

the assignment :

x 1 ← F , x 2 ← F , x 3 ← T 一个为真的赋值

will make the above formula true .

(-x 1 , -x 2 , x 3 ) represents x 1 ← F , x 2 ← F , x 3 ← T

If there is at least one assignment which

satisfies a formula, then we say that this

formula is satisfiable; otherwise, it is

unsatisfiable.

An unsatisfiable formula : 不可满足的公式

x 1 v x 2

& x 1 v -x 2

& -x 1 v x 2

& -x 1 v -x 2

Definition of the satisfiability problem:

Given a Boolean formula, determine whether this formula is satisfiable or not.

A literal : x i or -x i 文字

A clause : x 1 v x 2 v -x 3 = Ci 析取式作为子句

A formula : conjunctive normal form 合取范式作为一个公式

C 1 & C 2 & … & C m

The resolution principle 消除原理

A nondeterministic algorithm terminates

unsuccessfully iff there exist no a set of

choices leading to a success signal.

The time required for choice(1 : n) is O(1).

A deterministic interpretation of a non-

deterministic algorithm can be made by

allowing unbounded parallelism in computation.

Nondeterministic operations and functions

[Horowitz 1998]

Choice(S) : arbitrarily chooses one of the elements in set S

Failure : an unsuccessful completion

Success : a successful completion

Nonderministic searchingalgorithm:

j ← choice(1 : n) /* guessing */

if A(j) = x then success /* checking */

else failure

Example 1

Sorting problem

B ← 0

/* guessing */

for i = 1 to n do

j ← choice(1 : n)

if B[j] ≠ 0 then failure

B[j] = A[i]

/* checking */

for i = 1 to n-1 do

if B[i] > B[i+1] then failure

success

Example 2

N Queens problem

N-QUEEN (input n : integer; output B : array[1..n] of integer)

/* B[i] = the row of the queen in the ith column. -1 initially */

{

B← -1;

/* guessing */

for i = 1 to n do

j ← choice(1 : n)

B[i]=j

/* checking */

for i = 1 to n do

if (attacked(i, B) ) then failure

success

}

Concepts of NP Completeness （NP完全问题的概念）

If any NPC problem can be solved in polynomial time,

then all NP problems can be solved in polynomial time. (NP = P)

Cooks theorem

NP = P iff the satisfiability problem is a P problem.

SAT is NP-complete.

It is the first NP-complete problem.

Every NP problem reduces to SAT.

SAT is NP-complete

(1) SAT is an NP algorithm.

(2) SAT is NP-hard:

Every NP algorithm can be transformed in polynomial time to SAT [Horowitz 1998]

such that SAT is satisfiable if and only if the answer for the original NP problem is “YES”.

That is, every NP problem SAT .

By (1) and (2), SAT is NP-complete.