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

优化问题:已知一个点集合,找出从任何点v0开始的最短回路。

2.Decision version:

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

判定问题:已知一个点集合,是否存在从任何点v0开始的回路,其总长度小于已知的常数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.

 
 

一个有名的不是NP问题的判定问题是停机问题(Halting problem)


另一个问题是一阶谓词演算可满足性问题(first-order predicate calculus problem)

都是不可判定问题(undecidable problem)


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.

库克定理:当且仅当可满足性问题是P问题,那么NP = P。

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.

 
 

 





 
 


 
 


 
 

 
 

 
 

 
 

 
 

 
 



分类: 算法

发表评论

电子邮件地址不会被公开。 必填项已用*标注