Phase Transitions in the Random 3-SAT Problem and the Random NK Landscape Model
| Seminar
2007/04/09 13:44
April 6th, 2007
First of all, Prof. Kim explained about Boolean algebra. In Boolean algebra, there are Boolean expressions and Boolean functions. Boolean function is a function meaning f:B^n → B. The values of functions are 0 or 1. And Boolean expression in the variables x1, x2, …, xn is 0, 1, x1, …, xn. The characteristic of Boolean expression is that if E1 and E2 are Boolean expression, then ~E1 (not E1), E1 ∧ E2, and E1 ∨ E2 are also Boolean expressions. Also there is a theorem that every Boolean function can be represented by a Boolean expression.
More important note is that Boolean function can be represented as CNF (Conjunctive Normal Form). For example, Boolean function F(X,Y,Z) can be written as F(X,Y,Z)=(X∧Y∧Z)∨(X∧Y∧~Z)∨(~X∧Y∧Z). And we define k-clause as (y_1∨y_2∨… ∨y_k) for k strictly distinct literals y_1,…,y_k. A clause is a k-clause for some k. Then a CNF is a conjunction of clauses and every Boolean formula can be represented by a CNF.
A Boolean formula F is satisfiable if F≢0, that is there is x∉{0,1}^n such that F(x)≠0. And, similarly, a CNF F is satisfiable if F≢0, that is there is x∉{0,1}^n such that F(x)≠0. Satisfiability problem is that given CNF, we find out whether or not the CNF is satisfiable. It can be reduced to “Clique problem” which is also NP complete problem. If we solve one of NPC (NP-Complete) problems, then other problems in same group can be solved, too.
After attending that presentation, I was afraid because his speaking is much related to mathematics. He is a professor in math. Even though I studied much about computer algorithms, those works looked like very hard. Anyway, he researched in AT&T Bell Laboratory and he moved to Microsoft Research to study math. There is math laboratory called “Theory Group” in MSR. He said that he was invited from MSR so I envied him. But he came back to Korea last September. Though he was the first Korean who researched in MSR, Washington, he didn’t keep the research at there. I have no idea about why he came back.
In short, NPC problem is very hard and has no complete solution but in some cases. It’s very creative and challengeable work to solve that kind of problems.
First of all, Prof. Kim explained about Boolean algebra. In Boolean algebra, there are Boolean expressions and Boolean functions. Boolean function is a function meaning f:B^n → B. The values of functions are 0 or 1. And Boolean expression in the variables x1, x2, …, xn is 0, 1, x1, …, xn. The characteristic of Boolean expression is that if E1 and E2 are Boolean expression, then ~E1 (not E1), E1 ∧ E2, and E1 ∨ E2 are also Boolean expressions. Also there is a theorem that every Boolean function can be represented by a Boolean expression.
More important note is that Boolean function can be represented as CNF (Conjunctive Normal Form). For example, Boolean function F(X,Y,Z) can be written as F(X,Y,Z)=(X∧Y∧Z)∨(X∧Y∧~Z)∨(~X∧Y∧Z). And we define k-clause as (y_1∨y_2∨… ∨y_k) for k strictly distinct literals y_1,…,y_k. A clause is a k-clause for some k. Then a CNF is a conjunction of clauses and every Boolean formula can be represented by a CNF.
A Boolean formula F is satisfiable if F≢0, that is there is x∉{0,1}^n such that F(x)≠0. And, similarly, a CNF F is satisfiable if F≢0, that is there is x∉{0,1}^n such that F(x)≠0. Satisfiability problem is that given CNF, we find out whether or not the CNF is satisfiable. It can be reduced to “Clique problem” which is also NP complete problem. If we solve one of NPC (NP-Complete) problems, then other problems in same group can be solved, too.
After attending that presentation, I was afraid because his speaking is much related to mathematics. He is a professor in math. Even though I studied much about computer algorithms, those works looked like very hard. Anyway, he researched in AT&T Bell Laboratory and he moved to Microsoft Research to study math. There is math laboratory called “Theory Group” in MSR. He said that he was invited from MSR so I envied him. But he came back to Korea last September. Though he was the first Korean who researched in MSR, Washington, he didn’t keep the research at there. I have no idea about why he came back.
In short, NPC problem is very hard and has no complete solution but in some cases. It’s very creative and challengeable work to solve that kind of problems.
이올린에 북마크하기
