//p4
프로그램 x와 x의 수행 단계를 출력하는 프로그램 y
두 프로그램 x, y가 있다. 주어진 것은 x이다. (x라는 컴퓨터 프로그램.)
x : 입력없이 작동하면서 정지하는(유한 단계 안에 끝나는) 프로그램. (이것들은 알려져 있다. 그 외는 알려져 있지 않다.)
y는 그걸 계산한다. 어떻게 계산하느냐?
프로그램 y를 만드는데 그 과정은,
(1) x를 복사
(2) 추가로 변수 count 이용 (변수 하나를 정의)
(3) x의 명령(instruction) 하나 수행할때마다 count 증가하도록 설정
(4) y 수행 마치기 바로 직전에 count 값 출력
(x의 size) = a < (y의 size) = b
y의 사이즈가 당연히 크다...?
y가 출력하는 값
여기서
는 계산가능
따라서 x의 최대수행단계 계산가능.
BB(b)는,
사이즈가 최대 b인 프로그램이면서
정지하는 것이 확실하고
정지할 때 양의 정수 하나 출력하는
입력 없이 작동하는
프로그램들이 출력하는 값들 중 최대값
//p5
일단 S는 입력 없이 작동한다는 것 외엔 아무것도 모르는 프로그램이다.
따라서 (= 이전 슬라이드(p4)에서 설명한 과정에 의하면) 입력 없이 작동하는 임의의 프로그램 S가 주어지면, S의 size는 쉽게 알 수 있는데, 그 size가 c라 한다면
(1) 만일 S가 유한단계 작동 후 정지하는 프로그램이면, 1번 결과를 이용해 최대 수행단계가 얼마인지 계산 가능. 그 값을 d라 한다.
2. (fact -> 다음 슬라이드) 입력 없이 작동하는 임의의 프로그램 S를 줄 때 S가 무한루프를 도는지 아니면 유한단계 작동하고 정지하는지 계산 불가능하다. 즉 알고리즘이 존재하지 않는다.
이건 다음 슬라이드에서 얘기할것이다.
1번 결과를 이용해 이 fact에 모순이 됨을 보임. How?
//p6
S를 수행시키고 d까지 끝나지 않으면 무한루프를 도는 프로그램.
즉, 무한루프 도는지 아닌지 판별가능!
-> fact에 모순.
모순,contradiction
d는
만일 S가 정지하는 프로그램이라면 "1번 결과"에 의해 계산이 가능
물론 S는 정지하지 않고 무한루프 도는 프로그램일 수도 있지만, "중요한 것"은 S가 "정지하는 프로그램"인 경우는 100% 계산 가능하다는 것
따라서 명제 p는 참이고 BB(n)은 계산 불가능하다
명제 p: 모든 양의 정수 n에 대해서 BB(n)≤f(n)이면서 계산 가능한 f(n)은 존재하지 않는다
명제 q: BB(n)은 계산 불가능하다
//p7
P와 NP가 다르다는 것의 의미 1
.... Our daily experience is that it is harder to solve a problem than it is to check the correctness of a solution (e.g., think of either a puzzle or a homework assignment). Is this experience merely a coincidence or does it represent a fundamental fact of life (i.e., a property of the world)? Could you imagine a world in which solving any problem is not significantly harder than checking a solution to it? Would the term "solving a problem" not lose its meaning in such a hypothetical and impossible in our opinion) world? The denial of the plausibility of such a hypothetical world (in which "solving" is not harder than "checking") is what “P different from NP" actually means, where P represents tasks that are efficiently solvable and NP represents tasks for which solutions can be efficiently checked.
일상적 경험으론 (문제를 푸는 것 "solving")이 (정답인지 체크하는 것 "checking")보다 어렵다. 이게 단순히 우연의 일치(coincidence)인가, 세상의 특징인가? .... 혹시 그런 (푸는 것과 확인하는 것의 난이도의) 차이가 없는 세상을 상상할 수 있는가?
학교에선 d/l가능 외부에선 모르겠음
Invitation to complexity theory O. Goldrecich, XRDS Crossroads - The ACM Magazine for students March, 2012
//p8
P와 NP가 다르다는 것의 의미 2
문제 A
명제 x가 주어질 때
- 증명하는 것 (즉, x가
정리,theorem임을 보이는 것
문제 B
명제 x와 그 명제가 정리임을 보여주는
증명,proof y가 주어질 때
- y가 x의 타당한 증명이라는 것을 보이는 것
The mathematically (or theoretically) inclined reader may also consider the task of proving theorems versus the task of verifying the validity of proofs. Indeed, finding proofs is a special type of the aforementioned task of "solving a problem" (and verifying the validity of proofs is a corresponding case of checking correctness). Again, "P different from NP" means that there are theorems that are harder to prove than to be convinced of their correctness when presented with a proof. This means that the notion of a "proof" is meaningful; that is, proofs do help when seeking to be convinced of the correctness of assertions. Here NP represents sets of assertions that can be efficiently verified with the help of adequate proofs, and P represents sets of assertions that can be efficiently verified from scratch (i.e., without proofs).
//p9
계산문제는 언제 어려워지는가? (4장)
어떤 조건(들)이 만족할 때? (cf. 시간 - 언제 시작하는가? 에서의 의미와 다름)
3CNF satisfiability problem
불리언변수:
....true/false, 1/0 값들
리터럴(literal):
다음 두가지 모두 리터럴.
① 불리언변수
② ~(불리언변수)
예)
모든 리터럴은 불리언변수인가? 그렇지 않을 가능성이 있다. - 앞에 부정이 붙은 것이 있으므로
모든 불리언변수는 리터럴인가? 그럴 수 있다.
절(clause) : 한 개 이상의 리터럴들이 or로 연결된 것.
예)
x1 or ~x2
~x1
x1 or x2 or x3 or ~x4
논리식(formula) : 한 개 이상의 절들이 and로 연결된 것.
예)
(x1 or ~x2) and x3
(x1 or x2) and (x3 or ~x4 or x5) and ~x6
리터럴,literal
절,clause
논리식,formula (아마 적형식,wff과 동일? chk)
//p10
3CNF formula: 절들 안에 정확히 세 개의 리터럴들이 있는 formula(논리식).
conjunctive -이건 and라는 뜻.
normal
form
예) (x
1 or ~x
2 or x
3) and (x
1 or x
2 or x
3)
3CNF satisfiability problem (충족가능성문제)
입력: 3CNF formula f
출력: 만일 f 안에 있는 불리언변수들에
true나 false를 대입해서
f가 true가 되는 것이 가능하면 yes,
그렇지 않으면 no.
진리값(truth value)
- and : 연결된 것 "모두" true이면 true
- or : 연결된 것 중 하나만 true이면 true
- ~ : true이면 false, false이면 true
예) f
1 = (x
1 or ~x
2 or x
3) and (x
1 or x
2 or ~x
3)
x1=T, x2=T, x3=F 이면 f1=T 이므로 yes
f2 = (x1 or x1 or x1) and (~x1 or ~x1 or ~x1) - no
//p11
3CNF 충족가능성 문제의 구조 특성 1
3CNF 충족가능성문제는 NP의 원소 - 그 이유는? (검증이 효율적/쉽게 되기 때문 - 그런데 그 말이 무슨 의미인지 명확하게 설명하면 다음과 같음)
이 문제의 인스턴스들 중 답이 yes인 것 하나, 즉 "yes 인스턴스"와
답을 yes가 되게 하는 것 (certificate이라고 부름)을 주면,
정말 답이 yes라는 것의 "검증"이 다항식 단계 안에 가능함 - 즉 "효율적으로 검증이 됨"
예를 들어, f = (x
1 or x
2 or ~x
3) and (~x
1 or ~x
3 or x
4) and (x
2 or x
3 or ~x
3)와
이 3CNF 논리식이 "true"가 되게 만드는 각 변수들의 값, 즉 certificate으로
x1=T, x2=F, x3=F, x4=F 이렇게 주어지면
f 안에 있는 변수들에 certificate으로 주어진 값들 대입하여 정말 f가 true가 되는지 그래서 yes 인스턴스가 정말 맞는지 검증하는 것은 "쉽게" 가능함!
3CNF 충족가능성 문제가 P의 원소인가? "아직 모름!" 두 가지 가능성
(1) 만일 그렇다면, P = NP
(2) 만일 그렇지 않다면, P ≠ NP
이것들은 증명되어 있음.
cf. co-NP는 답이 no인 것에 초점을 맞춘다