Share
Sign In
P Class, NP Class, NP Complete
P Class
정의.
Definition 13.3 The Class P
P is the class of decision problems that are polynomially bounded.
P is the class of decision problems that are polynomially bounded.
Definition 13.2 Polynomially bounded
An algorithm is said to be polynomially Bounded if its worst-case complexity is bounded by a polynomial function of the input size.
A problem is said to be polynomially bounded if there is a polynomially bounded algorithm for it.
An algorithm is said to be polynomially Bounded if its worst-case complexity is bounded by a polynomial function of the input size.
A problem is said to be polynomially bounded if there is a polynomially bounded algorithm for it.
간단하게 말해 어떤 문제에 대해 polynomially time algorithm이 존재할 때, 그 문제는 P Class에 속한다고 할 수 있습니다. 이때 알고리즘이 P class가 아닌 문제가 P class에 속하는 것 입니다.
polynomially time algorithm(다항 시간 알고리즘) 이란 Worst-case에서의 시간복잡도가 N^a 으로 정의 되는 것을 말합니다. (단, a는 상수)
우리가 지금까지 배운 알고리즘은 모두 O(n^a)으로 정의할 수 있으니 그와 관련된 문제는 P class에 속한다고 할 수 있습니다.
P class의 polynomially time algorithm 은 다른말로 Deterministic Polynomially time의 알고리즘이라고 할 수 있습니다. 이는 추후에 나올 NP class와 비교하면 그 이유를 알 수 있습니다.
NP Class
정의.
Definition 13.5 The class NP
NP is the class decision problems for which there is a polynomially bounded nondeterministic algorithm. (NP: Nondeterministic Polynomially Bounded.)
NP is the class decision problems for which there is a polynomially bounded nondeterministic algorithm. (NP: Nondeterministic Polynomially Bounded.)
Definition 13.4 Nondeterministic algorithm
A nondeterministic algorithm has two phases and an output step:
1. Nondeterministic "guessing" Phase:
Arbitrary string of characters, s, is written. (A solution is proposed.)
2. Deterministic "verifying" Phase:
Read the decision problem's input and optionally s.
Returns a value true or false, or it may get in an infinite loop.
3. Output step:
If the verifying phase returned true, the algorithm outputs yes.
Otherwise, there is no output.
A nondeterministic algorithm has two phases and an output step:
1. Nondeterministic "guessing" Phase:
Arbitrary string of characters, s, is written. (A solution is proposed.)
2. Deterministic "verifying" Phase:
Read the decision problem's input and optionally s.
Returns a value true or false, or it may get in an infinite loop.
3. Output step:
If the verifying phase returned true, the algorithm outputs yes.
Otherwise, there is no output.
이론.
Theorem 13.1
Previous sample problems are all in NP
Previous sample problems are all in NP
Theorem 13.2
P \subseteq NP.
P \subseteq NP.
proof.
A deterministic algorithm is a special case if a nondeterministic algorithm (executing only the second phase.)
NP class 는 간단하게 말하면 그 문제를 해결하는 nondeterministic polynomially time algorithm 이 존재한다면, 그 문제는 NP class에 속한다고 할 수 있습니다.
p class 의 정의와 비슷하지만 Nondeterministic이라는 단어가 이해되지 않을 수 있습니다.
Nondeterministic 은 "비결정론적"이라는 뜻인데, 비결정론적 알고리즘은 같은 입력을 주더라도 매번 다른 과정을 거쳐 다른 결과를 도출하는 알고리즘을 말합니다.
Nondeterministic 은 "비결정론적"이라는 뜻인데, 비결정론적 알고리즘은 같은 입력을 주더라도 매번 다른 과정을 거쳐 다른 결과를 도출하는 알고리즘을 말합니다.
그렇다면 결정론적 알고리즘은 예측한 그대로 동작하는 알고리즘이다. 같은 입력을 넣었을 때 매번 같은 과정을 거쳐 같은 결과를 도출하는 알고리즘을 뜻합니다.
이론 13.2에 의하면 P는 NP에 부분집합이거나 같습니다. P class에 문제가 NP에 모두 속한다는 뜻입니다.
NP Hard & NP Complete
정의.
Definition 13.7 NP-hard and NP-complete
A problem Q is NP hard if every problem P in NP is reducible to Q; that is, P \le {_PQ}. A problem Q is NP-Complete if it is in NP and NP-hard.
- Being NP-hard constitutes a lower bound on the problem.
- Being in NP constitutes an upper bound.
A problem Q is NP hard if every problem P in NP is reducible to Q; that is, P \le {_PQ}. A problem Q is NP-Complete if it is in NP and NP-hard.
- Being NP-hard constitutes a lower bound on the problem.
- Being in NP constitutes an upper bound.
Definition 13.6 Polynomial reduction and reducibility
Let T be a function from the input set for a decision problem P into the input set for a decision problem Q. T is a polynomial reduction (also called a polynomially transformation) from P to Q if all of the following hold:
1. T can be computed in polynomially bounded time.
2. For every string x, if x is a yes input for P, then T(x) is a yes input for Q.
3. For every string x, if x is a no input for P, then T(x) is a no input for Q.
it is usually easier to prove the contrapositive of part 3.
3'. For every x, if T(x) is a yes input for Q, then x, is a yes input for P.
problem P is polynomially reducible (also called polynomially transformable) to Q if there exists a polynomially transformation from P to Q. (We usually just say P is reducible to Q)
The notation
P \le {_pQ}
is used to indicate that P is reducible to Q.
P \le {_pQ} \iff Q is at least as hard to solve as P.
Let T be a function from the input set for a decision problem P into the input set for a decision problem Q. T is a polynomial reduction (also called a polynomially transformation) from P to Q if all of the following hold:
1. T can be computed in polynomially bounded time.
2. For every string x, if x is a yes input for P, then T(x) is a yes input for Q.
3. For every string x, if x is a no input for P, then T(x) is a no input for Q.
it is usually easier to prove the contrapositive of part 3.
3'. For every x, if T(x) is a yes input for Q, then x, is a yes input for P.
problem P is polynomially reducible (also called polynomially transformable) to Q if there exists a polynomially transformation from P to Q. (We usually just say P is reducible to Q)
The notation
P \le {_pQ}
is used to indicate that P is reducible to Q.
P \le {_pQ} \iff Q is at least as hard to solve as P.
Theorem 13.3
If P \le {_pQ} and Q is in P, then P is in P.
If P \le {_pQ} and Q is in P, then P is in P.
Theorem 13.4
If any NP-complete problem is in P, them P = NP.
How valuable it would be to find a polynomially bounded algorithm for any NP-complete problem.
How unlikely it is that such an algorithm exists because there are so many problems in NP for which polynomially bounded algorithms have been sought without success.
If any NP-complete problem is in P, them P = NP.
How valuable it would be to find a polynomially bounded algorithm for any NP-complete problem.
How unlikely it is that such an algorithm exists because there are so many problems in NP for which polynomially bounded algorithms have been sought without success.
정의가 엄청 길어 어려워보이지만 간단하게 말하면 NP complete problem 은 NP class 와 NP Hard, 두가지 조건을 충족해야한다는 것입니다. 그렇다면 NP complete problem을 아려면 NP hard에 대해서 알아야겠죠.
NP hard는 NP class에 있는 모든 문제가 어떤 문제 Q로 Reducible 하다면, 그문제 Q는 NP hard 이다고 말합니다.
NP hard는 NP class에 있는 모든 문제가 어떤 문제 Q로 Reducible 하다면, 그문제 Q는 NP hard 이다고 말합니다.
우리는 polynomial Reduction을 polynomially transformation이라고 말할 수 있는데, 그림 13.2를 봐 봅시다. p라는 문제의 인풋인 x가 들어갔을 때 Transformation function T를 만나게 됩니다. 이 아웃풋인 T(x)는 다시 Q의 인풋이 되게되고,
이때 Transformation funcition은 P의 인풋을 Q의 인풋으로 바꿔주는 역할을 합니다.
다시 P 라는 문제를 Q라는 문제로 바꾸어서 Q 문제를 해결(그림에선 yes)하게 된다면 P의 문제도 해결(yes)하게 됩니다. 반대로 Q라는 문제로 바꾸어서 해결하지 못했을 때(no) P라는 문제도 해결하지 못하게 됩니다.
즉 우리는 Q를 해결하려는 알고리즘으로 P의 문제를 푼것이니, Q 문제가 더 어렵거나 같은 수준으로 어렵다고 할 수 있습니다.
위와같은 상황을 "Problem P is reducible to Q" 라고 말할 수 있습니다.
NP hard의 정의를 다시한번 봐봅시다. NP class에 있는 모든 문제가 어떤문제 Q로 reducible 하다면, 그 문제는 NP Hard 이다.
그럼 다시 NP complete문제로 돌아가 봅시다.
NP class에 속해있으면서 NP hard이면 NP complete 문제라고 합니다.
알고리즘으로 돌아가기
Algorithm
메인으로 돌아아기
P Class
정의.
Definition 13.3 The Class P
P is the class of decision problems that are polynomially bounded.
P is the class of decision problems that are polynomially bounded.
Definition 13.2 Polynomially bounded
An algorithm is said to be polynomially Bounded if its worst-case complexity is bounded by a polynomial function of the input size.
A problem is said to be polynomially bounded if there is a polynomially bounded algorithm for it.
An algorithm is said to be polynomially Bounded if its worst-case complexity is bounded by a polynomial function of the input size.
A problem is said to be polynomially bounded if there is a polynomially bounded algorithm for it.
간단하게 말해 어떤 문제에 대해 polynomially time algorithm이 존재할 때, 그 문제는 P Class에 속한다고 할 수 있습니다. 이때 알고리즘이 P class가 아닌 문제가 P class에 속하는 것 입니다.
polynomially time algorithm(다항 시간 알고리즘) 이란 Worst-case에서의 시간복잡도가 N^a 으로 정의 되는 것을 말합니다. (단, a는 상수)
우리가 지금까지 배운 알고리즘은 모두 O(n^a)으로 정의할 수 있으니 그와 관련된 문제는 P class에 속한다고 할 수 있습니다.
P class의 polynomially time algorithm 은 다른말로 Deterministic Polynomially time의 알고리즘이라고 할 수 있습니다. 이는 추후에 나올 NP class와 비교하면 그 이유를 알 수 있습니다.
NP Class
정의.
Definition 13.5 The class NP
NP is the class decision problems for which there is a polynomially bounded nondeterministic algorithm. (NP: Nondeterministic Polynomially Bounded.)
NP is the class decision problems for which there is a polynomially bounded nondeterministic algorithm. (NP: Nondeterministic Polynomially Bounded.)
Definition 13.4 Nondeterministic algorithm
A nondeterministic algorithm has two phases and an output step:
1. Nondeterministic "guessing" Phase:
Arbitrary string of characters, s, is written. (A solution is proposed.)
2. Deterministic "verifying" Phase:
Read the decision problem's input and optionally s.
Returns a value true or false, or it may get in an infinite loop.
3. Output step:
If the verifying phase returned true, the algorithm outputs yes.
Otherwise, there is no output.
A nondeterministic algorithm has two phases and an output step:
1. Nondeterministic "guessing" Phase:
Arbitrary string of characters, s, is written. (A solution is proposed.)
2. Deterministic "verifying" Phase:
Read the decision problem's input and optionally s.
Returns a value true or false, or it may get in an infinite loop.
3. Output step:
If the verifying phase returned true, the algorithm outputs yes.
Otherwise, there is no output.
이론.
Theorem 13.1
Previous sample problems are all in NP
Previous sample problems are all in NP
Theorem 13.2
P \subseteq NP.
P \subseteq NP.
proof.
A deterministic algorithm is a special case if a nondeterministic algorithm (executing only the second phase.)
NP class 는 간단하게 말하면 그 문제를 해결하는 nondeterministic polynomially time algorithm 이 존재한다면, 그 문제는 NP class에 속한다고 할 수 있습니다.
p class 의 정의와 비슷하지만 Nondeterministic이라는 단어가 이해되지 않을 수 있습니다.
Nondeterministic 은 "비결정론적"이라는 뜻인데, 비결정론적 알고리즘은 같은 입력을 주더라도 매번 다른 과정을 거쳐 다른 결과를 도출하는 알고리즘을 말합니다.
Nondeterministic 은 "비결정론적"이라는 뜻인데, 비결정론적 알고리즘은 같은 입력을 주더라도 매번 다른 과정을 거쳐 다른 결과를 도출하는 알고리즘을 말합니다.
그렇다면 결정론적 알고리즘은 예측한 그대로 동작하는 알고리즘이다. 같은 입력을 넣었을 때 매번 같은 과정을 거쳐 같은 결과를 도출하는 알고리즘을 뜻합니다.
이론 13.2에 의하면 P는 NP에 부분집합이거나 같습니다. P class에 문제가 NP에 모두 속한다는 뜻입니다.
NP Hard & NP Complete
정의.
Definition 13.7 NP-hard and NP-complete
A problem Q is NP hard if every problem P in NP is reducible to Q; that is, P \le {_PQ}. A problem Q is NP-Complete if it is in NP and NP-hard.
- Being NP-hard constitutes a lower bound on the problem.
- Being in NP constitutes an upper bound.
A problem Q is NP hard if every problem P in NP is reducible to Q; that is, P \le {_PQ}. A problem Q is NP-Complete if it is in NP and NP-hard.
- Being NP-hard constitutes a lower bound on the problem.
- Being in NP constitutes an upper bound.
Definition 13.6 Polynomial reduction and reducibility
Let T be a function from the input set for a decision problem P into the input set for a decision problem Q. T is a polynomial reduction (also called a polynomially transformation) from P to Q if all of the following hold:
1. T can be computed in polynomially bounded time.
2. For every string x, if x is a yes input for P, then T(x) is a yes input for Q.
3. For every string x, if x is a no input for P, then T(x) is a no input for Q.
it is usually easier to prove the contrapositive of part 3.
3'. For every x, if T(x) is a yes input for Q, then x, is a yes input for P.
problem P is polynomially reducible (also called polynomially transformable) to Q if there exists a polynomially transformation from P to Q. (We usually just say P is reducible to Q)
The notation
P \le {_pQ}
is used to indicate that P is reducible to Q.
P \le {_pQ} \iff Q is at least as hard to solve as P.
Let T be a function from the input set for a decision problem P into the input set for a decision problem Q. T is a polynomial reduction (also called a polynomially transformation) from P to Q if all of the following hold:
1. T can be computed in polynomially bounded time.
2. For every string x, if x is a yes input for P, then T(x) is a yes input for Q.
3. For every string x, if x is a no input for P, then T(x) is a no input for Q.
it is usually easier to prove the contrapositive of part 3.
3'. For every x, if T(x) is a yes input for Q, then x, is a yes input for P.
problem P is polynomially reducible (also called polynomially transformable) to Q if there exists a polynomially transformation from P to Q. (We usually just say P is reducible to Q)
The notation
P \le {_pQ}
is used to indicate that P is reducible to Q.
P \le {_pQ} \iff Q is at least as hard to solve as P.
Theorem 13.3
If P \le {_pQ} and Q is in P, then P is in P.
If P \le {_pQ} and Q is in P, then P is in P.
Theorem 13.4
If any NP-complete problem is in P, them P = NP.
How valuable it would be to find a polynomially bounded algorithm for any NP-complete problem.
How unlikely it is that such an algorithm exists because there are so many problems in NP for which polynomially bounded algorithms have been sought without success.
If any NP-complete problem is in P, them P = NP.
How valuable it would be to find a polynomially bounded algorithm for any NP-complete problem.
How unlikely it is that such an algorithm exists because there are so many problems in NP for which polynomially bounded algorithms have been sought without success.
정의가 엄청 길어 어려워보이지만 간단하게 말하면 NP complete problem 은 NP class 와 NP Hard, 두가지 조건을 충족해야한다는 것입니다. 그렇다면 NP complete problem을 아려면 NP hard에 대해서 알아야겠죠.
NP hard는 NP class에 있는 모든 문제가 어떤 문제 Q로 Reducible 하다면, 그문제 Q는 NP hard 이다고 말합니다.
NP hard는 NP class에 있는 모든 문제가 어떤 문제 Q로 Reducible 하다면, 그문제 Q는 NP hard 이다고 말합니다.
우리는 polynomial Reduction을 polynomially transformation이라고 말할 수 있는데, 그림 13.2를 봐 봅시다. p라는 문제의 인풋인 x가 들어갔을 때 Transformation function T를 만나게 됩니다. 이 아웃풋인 T(x)는 다시 Q의 인풋이 되게되고,
이때 Transformation funcition은 P의 인풋을 Q의 인풋으로 바꿔주는 역할을 합니다.
다시 P 라는 문제를 Q라는 문제로 바꾸어서 Q 문제를 해결(그림에선 yes)하게 된다면 P의 문제도 해결(yes)하게 됩니다. 반대로 Q라는 문제로 바꾸어서 해결하지 못했을 때(no) P라는 문제도 해결하지 못하게 됩니다.
즉 우리는 Q를 해결하려는 알고리즘으로 P의 문제를 푼것이니, Q 문제가 더 어렵거나 같은 수준으로 어렵다고 할 수 있습니다.
위와같은 상황을 "Problem P is reducible to Q" 라고 말할 수 있습니다.
NP hard의 정의를 다시한번 봐봅시다. NP class에 있는 모든 문제가 어떤문제 Q로 reducible 하다면, 그 문제는 NP Hard 이다.
그럼 다시 NP complete문제로 돌아가 봅시다.
NP class에 속해있으면서 NP hard이면 NP complete 문제라고 합니다.
알고리즘으로 돌아가기
Algorithm
메인으로 돌아아기
P Class
정의.
Definition 13.3 The Class P
P is the class of decision problems that are polynomially bounded.
P is the class of decision problems that are polynomially bounded.
Definition 13.2 Polynomially bounded
An algorithm is said to be polynomially Bounded if its worst-case complexity is bounded by a polynomial function of the input size.
A problem is said to be polynomially bounded if there is a polynomially bounded algorithm for it.
An algorithm is said to be polynomially Bounded if its worst-case complexity is bounded by a polynomial function of the input size.
A problem is said to be polynomially bounded if there is a polynomially bounded algorithm for it.
간단하게 말해 어떤 문제에 대해 polynomially time algorithm이 존재할 때, 그 문제는 P Class에 속한다고 할 수 있습니다. 이때 알고리즘이 P class가 아닌 문제가 P class에 속하는 것 입니다.
polynomially time algorithm(다항 시간 알고리즘) 이란 Worst-case에서의 시간복잡도가 N^a 으로 정의 되는 것을 말합니다. (단, a는 상수)
우리가 지금까지 배운 알고리즘은 모두 O(n^a)으로 정의할 수 있으니 그와 관련된 문제는 P class에 속한다고 할 수 있습니다.
P class의 polynomially time algorithm 은 다른말로 Deterministic Polynomially time의 알고리즘이라고 할 수 있습니다. 이는 추후에 나올 NP class와 비교하면 그 이유를 알 수 있습니다.
NP Class
정의.
Definition 13.5 The class NP
NP is the class decision problems for which there is a polynomially bounded nondeterministic algorithm. (NP: Nondeterministic Polynomially Bounded.)
NP is the class decision problems for which there is a polynomially bounded nondeterministic algorithm. (NP: Nondeterministic Polynomially Bounded.)
Definition 13.4 Nondeterministic algorithm
A nondeterministic algorithm has two phases and an output step:
1. Nondeterministic "guessing" Phase:
Arbitrary string of characters, s, is written. (A solution is proposed.)
2. Deterministic "verifying" Phase:
Read the decision problem's input and optionally s.
Returns a value true or false, or it may get in an infinite loop.
3. Output step:
If the verifying phase returned true, the algorithm outputs yes.
Otherwise, there is no output.
A nondeterministic algorithm has two phases and an output step:
1. Nondeterministic "guessing" Phase:
Arbitrary string of characters, s, is written. (A solution is proposed.)
2. Deterministic "verifying" Phase:
Read the decision problem's input and optionally s.
Returns a value true or false, or it may get in an infinite loop.
3. Output step:
If the verifying phase returned true, the algorithm outputs yes.
Otherwise, there is no output.
이론.
Theorem 13.1
Previous sample problems are all in NP
Previous sample problems are all in NP
Theorem 13.2
P \subseteq NP.
P \subseteq NP.
proof.
A deterministic algorithm is a special case if a nondeterministic algorithm (executing only the second phase.)
NP class 는 간단하게 말하면 그 문제를 해결하는 nondeterministic polynomially time algorithm 이 존재한다면, 그 문제는 NP class에 속한다고 할 수 있습니다.
p class 의 정의와 비슷하지만 Nondeterministic이라는 단어가 이해되지 않을 수 있습니다.
Nondeterministic 은 "비결정론적"이라는 뜻인데, 비결정론적 알고리즘은 같은 입력을 주더라도 매번 다른 과정을 거쳐 다른 결과를 도출하는 알고리즘을 말합니다.
Nondeterministic 은 "비결정론적"이라는 뜻인데, 비결정론적 알고리즘은 같은 입력을 주더라도 매번 다른 과정을 거쳐 다른 결과를 도출하는 알고리즘을 말합니다.
그렇다면 결정론적 알고리즘은 예측한 그대로 동작하는 알고리즘이다. 같은 입력을 넣었을 때 매번 같은 과정을 거쳐 같은 결과를 도출하는 알고리즘을 뜻합니다.
이론 13.2에 의하면 P는 NP에 부분집합이거나 같습니다. P class에 문제가 NP에 모두 속한다는 뜻입니다.
NP Hard & NP Complete
정의.
Definition 13.7 NP-hard and NP-complete
A problem Q is NP hard if every problem P in NP is reducible to Q; that is, P \le {_PQ}. A problem Q is NP-Complete if it is in NP and NP-hard.
- Being NP-hard constitutes a lower bound on the problem.
- Being in NP constitutes an upper bound.
A problem Q is NP hard if every problem P in NP is reducible to Q; that is, P \le {_PQ}. A problem Q is NP-Complete if it is in NP and NP-hard.
- Being NP-hard constitutes a lower bound on the problem.
- Being in NP constitutes an upper bound.
Definition 13.6 Polynomial reduction and reducibility
Let T be a function from the input set for a decision problem P into the input set for a decision problem Q. T is a polynomial reduction (also called a polynomially transformation) from P to Q if all of the following hold:
1. T can be computed in polynomially bounded time.
2. For every string x, if x is a yes input for P, then T(x) is a yes input for Q.
3. For every string x, if x is a no input for P, then T(x) is a no input for Q.
it is usually easier to prove the contrapositive of part 3.
3'. For every x, if T(x) is a yes input for Q, then x, is a yes input for P.
problem P is polynomially reducible (also called polynomially transformable) to Q if there exists a polynomially transformation from P to Q. (We usually just say P is reducible to Q)
The notation
P \le {_pQ}
is used to indicate that P is reducible to Q.
P \le {_pQ} \iff Q is at least as hard to solve as P.
Let T be a function from the input set for a decision problem P into the input set for a decision problem Q. T is a polynomial reduction (also called a polynomially transformation) from P to Q if all of the following hold:
1. T can be computed in polynomially bounded time.
2. For every string x, if x is a yes input for P, then T(x) is a yes input for Q.
3. For every string x, if x is a no input for P, then T(x) is a no input for Q.
it is usually easier to prove the contrapositive of part 3.
3'. For every x, if T(x) is a yes input for Q, then x, is a yes input for P.
problem P is polynomially reducible (also called polynomially transformable) to Q if there exists a polynomially transformation from P to Q. (We usually just say P is reducible to Q)
The notation
P \le {_pQ}
is used to indicate that P is reducible to Q.
P \le {_pQ} \iff Q is at least as hard to solve as P.
Theorem 13.3
If P \le {_pQ} and Q is in P, then P is in P.
If P \le {_pQ} and Q is in P, then P is in P.
Theorem 13.4
If any NP-complete problem is in P, them P = NP.
How valuable it would be to find a polynomially bounded algorithm for any NP-complete problem.
How unlikely it is that such an algorithm exists because there are so many problems in NP for which polynomially bounded algorithms have been sought without success.
If any NP-complete problem is in P, them P = NP.
How valuable it would be to find a polynomially bounded algorithm for any NP-complete problem.
How unlikely it is that such an algorithm exists because there are so many problems in NP for which polynomially bounded algorithms have been sought without success.
정의가 엄청 길어 어려워보이지만 간단하게 말하면 NP complete problem 은 NP class 와 NP Hard, 두가지 조건을 충족해야한다는 것입니다. 그렇다면 NP complete problem을 아려면 NP hard에 대해서 알아야겠죠.
NP hard는 NP class에 있는 모든 문제가 어떤 문제 Q로 Reducible 하다면, 그문제 Q는 NP hard 이다고 말합니다.
NP hard는 NP class에 있는 모든 문제가 어떤 문제 Q로 Reducible 하다면, 그문제 Q는 NP hard 이다고 말합니다.
우리는 polynomial Reduction을 polynomially transformation이라고 말할 수 있는데, 그림 13.2를 봐 봅시다. p라는 문제의 인풋인 x가 들어갔을 때 Transformation function T를 만나게 됩니다. 이 아웃풋인 T(x)는 다시 Q의 인풋이 되게되고,
이때 Transformation funcition은 P의 인풋을 Q의 인풋으로 바꿔주는 역할을 합니다.
다시 P 라는 문제를 Q라는 문제로 바꾸어서 Q 문제를 해결(그림에선 yes)하게 된다면 P의 문제도 해결(yes)하게 됩니다. 반대로 Q라는 문제로 바꾸어서 해결하지 못했을 때(no) P라는 문제도 해결하지 못하게 됩니다.
즉 우리는 Q를 해결하려는 알고리즘으로 P의 문제를 푼것이니, Q 문제가 더 어렵거나 같은 수준으로 어렵다고 할 수 있습니다.
위와같은 상황을 "Problem P is reducible to Q" 라고 말할 수 있습니다.
NP hard의 정의를 다시한번 봐봅시다. NP class에 있는 모든 문제가 어떤문제 Q로 reducible 하다면, 그 문제는 NP Hard 이다.
그럼 다시 NP complete문제로 돌아가 봅시다.
NP class에 속해있으면서 NP hard이면 NP complete 문제라고 합니다.
알고리즘으로 돌아가기
Algorithm
메인으로 돌아아기
P Class
정의.
Definition 13.3 The Class P
P is the class of decision problems that are polynomially bounded.
P is the class of decision problems that are polynomially bounded.
Definition 13.2 Polynomially bounded
An algorithm is said to be polynomially Bounded if its worst-case complexity is bounded by a polynomial function of the input size.
A problem is said to be polynomially bounded if there is a polynomially bounded algorithm for it.
An algorithm is said to be polynomially Bounded if its worst-case complexity is bounded by a polynomial function of the input size.
A problem is said to be polynomially bounded if there is a polynomially bounded algorithm for it.
간단하게 말해 어떤 문제에 대해 polynomially time algorithm이 존재할 때, 그 문제는 P Class에 속한다고 할 수 있습니다. 이때 알고리즘이 P class가 아닌 문제가 P class에 속하는 것 입니다.
polynomially time algorithm(다항 시간 알고리즘) 이란 Worst-case에서의 시간복잡도가 N^a 으로 정의 되는 것을 말합니다. (단, a는 상수)
우리가 지금까지 배운 알고리즘은 모두 O(n^a)으로 정의할 수 있으니 그와 관련된 문제는 P class에 속한다고 할 수 있습니다.
P class의 polynomially time algorithm 은 다른말로 Deterministic Polynomially time의 알고리즘이라고 할 수 있습니다. 이는 추후에 나올 NP class와 비교하면 그 이유를 알 수 있습니다.
NP Class
정의.
Definition 13.5 The class NP
NP is the class decision problems for which there is a polynomially bounded nondeterministic algorithm. (NP: Nondeterministic Polynomially Bounded.)
NP is the class decision problems for which there is a polynomially bounded nondeterministic algorithm. (NP: Nondeterministic Polynomially Bounded.)
Definition 13.4 Nondeterministic algorithm
A nondeterministic algorithm has two phases and an output step:
1. Nondeterministic "guessing" Phase:
Arbitrary string of characters, s, is written. (A solution is proposed.)
2. Deterministic "verifying" Phase:
Read the decision problem's input and optionally s.
Returns a value true or false, or it may get in an infinite loop.
3. Output step:
If the verifying phase returned true, the algorithm outputs yes.
Otherwise, there is no output.
A nondeterministic algorithm has two phases and an output step:
1. Nondeterministic "guessing" Phase:
Arbitrary string of characters, s, is written. (A solution is proposed.)
2. Deterministic "verifying" Phase:
Read the decision problem's input and optionally s.
Returns a value true or false, or it may get in an infinite loop.
3. Output step:
If the verifying phase returned true, the algorithm outputs yes.
Otherwise, there is no output.
이론.
Theorem 13.1
Previous sample problems are all in NP
Previous sample problems are all in NP
Theorem 13.2
P \subseteq NP.
P \subseteq NP.
proof.
A deterministic algorithm is a special case if a nondeterministic algorithm (executing only the second phase.)
NP class 는 간단하게 말하면 그 문제를 해결하는 nondeterministic polynomially time algorithm 이 존재한다면, 그 문제는 NP class에 속한다고 할 수 있습니다.
p class 의 정의와 비슷하지만 Nondeterministic이라는 단어가 이해되지 않을 수 있습니다.
Nondeterministic 은 "비결정론적"이라는 뜻인데, 비결정론적 알고리즘은 같은 입력을 주더라도 매번 다른 과정을 거쳐 다른 결과를 도출하는 알고리즘을 말합니다.
Nondeterministic 은 "비결정론적"이라는 뜻인데, 비결정론적 알고리즘은 같은 입력을 주더라도 매번 다른 과정을 거쳐 다른 결과를 도출하는 알고리즘을 말합니다.
그렇다면 결정론적 알고리즘은 예측한 그대로 동작하는 알고리즘이다. 같은 입력을 넣었을 때 매번 같은 과정을 거쳐 같은 결과를 도출하는 알고리즘을 뜻합니다.
이론 13.2에 의하면 P는 NP에 부분집합이거나 같습니다. P class에 문제가 NP에 모두 속한다는 뜻입니다.
NP Hard & NP Complete
정의.
Definition 13.7 NP-hard and NP-complete
A problem Q is NP hard if every problem P in NP is reducible to Q; that is, P \le {_PQ}. A problem Q is NP-Complete if it is in NP and NP-hard.
- Being NP-hard constitutes a lower bound on the problem.
- Being in NP constitutes an upper bound.
A problem Q is NP hard if every problem P in NP is reducible to Q; that is, P \le {_PQ}. A problem Q is NP-Complete if it is in NP and NP-hard.
- Being NP-hard constitutes a lower bound on the problem.
- Being in NP constitutes an upper bound.
Definition 13.6 Polynomial reduction and reducibility
Let T be a function from the input set for a decision problem P into the input set for a decision problem Q. T is a polynomial reduction (also called a polynomially transformation) from P to Q if all of the following hold:
1. T can be computed in polynomially bounded time.
2. For every string x, if x is a yes input for P, then T(x) is a yes input for Q.
3. For every string x, if x is a no input for P, then T(x) is a no input for Q.
it is usually easier to prove the contrapositive of part 3.
3'. For every x, if T(x) is a yes input for Q, then x, is a yes input for P.
problem P is polynomially reducible (also called polynomially transformable) to Q if there exists a polynomially transformation from P to Q. (We usually just say P is reducible to Q)
The notation
P \le {_pQ}
is used to indicate that P is reducible to Q.
P \le {_pQ} \iff Q is at least as hard to solve as P.
Let T be a function from the input set for a decision problem P into the input set for a decision problem Q. T is a polynomial reduction (also called a polynomially transformation) from P to Q if all of the following hold:
1. T can be computed in polynomially bounded time.
2. For every string x, if x is a yes input for P, then T(x) is a yes input for Q.
3. For every string x, if x is a no input for P, then T(x) is a no input for Q.
it is usually easier to prove the contrapositive of part 3.
3'. For every x, if T(x) is a yes input for Q, then x, is a yes input for P.
problem P is polynomially reducible (also called polynomially transformable) to Q if there exists a polynomially transformation from P to Q. (We usually just say P is reducible to Q)
The notation
P \le {_pQ}
is used to indicate that P is reducible to Q.
P \le {_pQ} \iff Q is at least as hard to solve as P.
Theorem 13.3
If P \le {_pQ} and Q is in P, then P is in P.
If P \le {_pQ} and Q is in P, then P is in P.
Theorem 13.4
If any NP-complete problem is in P, them P = NP.
How valuable it would be to find a polynomially bounded algorithm for any NP-complete problem.
How unlikely it is that such an algorithm exists because there are so many problems in NP for which polynomially bounded algorithms have been sought without success.
If any NP-complete problem is in P, them P = NP.
How valuable it would be to find a polynomially bounded algorithm for any NP-complete problem.
How unlikely it is that such an algorithm exists because there are so many problems in NP for which polynomially bounded algorithms have been sought without success.
정의가 엄청 길어 어려워보이지만 간단하게 말하면 NP complete problem 은 NP class 와 NP Hard, 두가지 조건을 충족해야한다는 것입니다. 그렇다면 NP complete problem을 아려면 NP hard에 대해서 알아야겠죠.
NP hard는 NP class에 있는 모든 문제가 어떤 문제 Q로 Reducible 하다면, 그문제 Q는 NP hard 이다고 말합니다.
NP hard는 NP class에 있는 모든 문제가 어떤 문제 Q로 Reducible 하다면, 그문제 Q는 NP hard 이다고 말합니다.
우리는 polynomial Reduction을 polynomially transformation이라고 말할 수 있는데, 그림 13.2를 봐 봅시다. p라는 문제의 인풋인 x가 들어갔을 때 Transformation function T를 만나게 됩니다. 이 아웃풋인 T(x)는 다시 Q의 인풋이 되게되고,
이때 Transformation funcition은 P의 인풋을 Q의 인풋으로 바꿔주는 역할을 합니다.
다시 P 라는 문제를 Q라는 문제로 바꾸어서 Q 문제를 해결(그림에선 yes)하게 된다면 P의 문제도 해결(yes)하게 됩니다. 반대로 Q라는 문제로 바꾸어서 해결하지 못했을 때(no) P라는 문제도 해결하지 못하게 됩니다.
즉 우리는 Q를 해결하려는 알고리즘으로 P의 문제를 푼것이니, Q 문제가 더 어렵거나 같은 수준으로 어렵다고 할 수 있습니다.
위와같은 상황을 "Problem P is reducible to Q" 라고 말할 수 있습니다.
NP hard의 정의를 다시한번 봐봅시다. NP class에 있는 모든 문제가 어떤문제 Q로 reducible 하다면, 그 문제는 NP Hard 이다.
그럼 다시 NP complete문제로 돌아가 봅시다.
NP class에 속해있으면서 NP hard이면 NP complete 문제라고 합니다.
알고리즘으로 돌아가기
Algorithm
메인으로 돌아아기
P Class
정의.
Definition 13.3 The Class P
P is the class of decision problems that are polynomially bounded.
P is the class of decision problems that are polynomially bounded.
Definition 13.2 Polynomially bounded
An algorithm is said to be polynomially Bounded if its worst-case complexity is bounded by a polynomial function of the input size.
A problem is said to be polynomially bounded if there is a polynomially bounded algorithm for it.
An algorithm is said to be polynomially Bounded if its worst-case complexity is bounded by a polynomial function of the input size.
A problem is said to be polynomially bounded if there is a polynomially bounded algorithm for it.
간단하게 말해 어떤 문제에 대해 polynomially time algorithm이 존재할 때, 그 문제는 P Class에 속한다고 할 수 있습니다. 이때 알고리즘이 P class가 아닌 문제가 P class에 속하는 것 입니다.
polynomially time algorithm(다항 시간 알고리즘) 이란 Worst-case에서의 시간복잡도가 N^a 으로 정의 되는 것을 말합니다. (단, a는 상수)
우리가 지금까지 배운 알고리즘은 모두 O(n^a)으로 정의할 수 있으니 그와 관련된 문제는 P class에 속한다고 할 수 있습니다.
P class의 polynomially time algorithm 은 다른말로 Deterministic Polynomially time의 알고리즘이라고 할 수 있습니다. 이는 추후에 나올 NP class와 비교하면 그 이유를 알 수 있습니다.
NP Class
정의.
Definition 13.5 The class NP
NP is the class decision problems for which there is a polynomially bounded nondeterministic algorithm. (NP: Nondeterministic Polynomially Bounded.)
NP is the class decision problems for which there is a polynomially bounded nondeterministic algorithm. (NP: Nondeterministic Polynomially Bounded.)
Definition 13.4 Nondeterministic algorithm
A nondeterministic algorithm has two phases and an output step:
1. Nondeterministic "guessing" Phase:
Arbitrary string of characters, s, is written. (A solution is proposed.)
2. Deterministic "verifying" Phase:
Read the decision problem's input and optionally s.
Returns a value true or false, or it may get in an infinite loop.
3. Output step:
If the verifying phase returned true, the algorithm outputs yes.
Otherwise, there is no output.
A nondeterministic algorithm has two phases and an output step:
1. Nondeterministic "guessing" Phase:
Arbitrary string of characters, s, is written. (A solution is proposed.)
2. Deterministic "verifying" Phase:
Read the decision problem's input and optionally s.
Returns a value true or false, or it may get in an infinite loop.
3. Output step:
If the verifying phase returned true, the algorithm outputs yes.
Otherwise, there is no output.
이론.
Theorem 13.1
Previous sample problems are all in NP
Previous sample problems are all in NP
Theorem 13.2
P \subseteq NP.
P \subseteq NP.
proof.
A deterministic algorithm is a special case if a nondeterministic algorithm (executing only the second phase.)
NP class 는 간단하게 말하면 그 문제를 해결하는 nondeterministic polynomially time algorithm 이 존재한다면, 그 문제는 NP class에 속한다고 할 수 있습니다.
p class 의 정의와 비슷하지만 Nondeterministic이라는 단어가 이해되지 않을 수 있습니다.
Nondeterministic 은 "비결정론적"이라는 뜻인데, 비결정론적 알고리즘은 같은 입력을 주더라도 매번 다른 과정을 거쳐 다른 결과를 도출하는 알고리즘을 말합니다.
Nondeterministic 은 "비결정론적"이라는 뜻인데, 비결정론적 알고리즘은 같은 입력을 주더라도 매번 다른 과정을 거쳐 다른 결과를 도출하는 알고리즘을 말합니다.
그렇다면 결정론적 알고리즘은 예측한 그대로 동작하는 알고리즘이다. 같은 입력을 넣었을 때 매번 같은 과정을 거쳐 같은 결과를 도출하는 알고리즘을 뜻합니다.
이론 13.2에 의하면 P는 NP에 부분집합이거나 같습니다. P class에 문제가 NP에 모두 속한다는 뜻입니다.
NP Hard & NP Complete
정의.
Definition 13.7 NP-hard and NP-complete
A problem Q is NP hard if every problem P in NP is reducible to Q; that is, P \le {_PQ}. A problem Q is NP-Complete if it is in NP and NP-hard.
- Being NP-hard constitutes a lower bound on the problem.
- Being in NP constitutes an upper bound.
A problem Q is NP hard if every problem P in NP is reducible to Q; that is, P \le {_PQ}. A problem Q is NP-Complete if it is in NP and NP-hard.
- Being NP-hard constitutes a lower bound on the problem.
- Being in NP constitutes an upper bound.
Definition 13.6 Polynomial reduction and reducibility
Let T be a function from the input set for a decision problem P into the input set for a decision problem Q. T is a polynomial reduction (also called a polynomially transformation) from P to Q if all of the following hold:
1. T can be computed in polynomially bounded time.
2. For every string x, if x is a yes input for P, then T(x) is a yes input for Q.
3. For every string x, if x is a no input for P, then T(x) is a no input for Q.
it is usually easier to prove the contrapositive of part 3.
3'. For every x, if T(x) is a yes input for Q, then x, is a yes input for P.
problem P is polynomially reducible (also called polynomially transformable) to Q if there exists a polynomially transformation from P to Q. (We usually just say P is reducible to Q)
The notation
P \le {_pQ}
is used to indicate that P is reducible to Q.
P \le {_pQ} \iff Q is at least as hard to solve as P.
Let T be a function from the input set for a decision problem P into the input set for a decision problem Q. T is a polynomial reduction (also called a polynomially transformation) from P to Q if all of the following hold:
1. T can be computed in polynomially bounded time.
2. For every string x, if x is a yes input for P, then T(x) is a yes input for Q.
3. For every string x, if x is a no input for P, then T(x) is a no input for Q.
it is usually easier to prove the contrapositive of part 3.
3'. For every x, if T(x) is a yes input for Q, then x, is a yes input for P.
problem P is polynomially reducible (also called polynomially transformable) to Q if there exists a polynomially transformation from P to Q. (We usually just say P is reducible to Q)
The notation
P \le {_pQ}
is used to indicate that P is reducible to Q.
P \le {_pQ} \iff Q is at least as hard to solve as P.
Theorem 13.3
If P \le {_pQ} and Q is in P, then P is in P.
If P \le {_pQ} and Q is in P, then P is in P.
Theorem 13.4
If any NP-complete problem is in P, them P = NP.
How valuable it would be to find a polynomially bounded algorithm for any NP-complete problem.
How unlikely it is that such an algorithm exists because there are so many problems in NP for which polynomially bounded algorithms have been sought without success.
If any NP-complete problem is in P, them P = NP.
How valuable it would be to find a polynomially bounded algorithm for any NP-complete problem.
How unlikely it is that such an algorithm exists because there are so many problems in NP for which polynomially bounded algorithms have been sought without success.
정의가 엄청 길어 어려워보이지만 간단하게 말하면 NP complete problem 은 NP class 와 NP Hard, 두가지 조건을 충족해야한다는 것입니다. 그렇다면 NP complete problem을 아려면 NP hard에 대해서 알아야겠죠.
NP hard는 NP class에 있는 모든 문제가 어떤 문제 Q로 Reducible 하다면, 그문제 Q는 NP hard 이다고 말합니다.
NP hard는 NP class에 있는 모든 문제가 어떤 문제 Q로 Reducible 하다면, 그문제 Q는 NP hard 이다고 말합니다.
우리는 polynomial Reduction을 polynomially transformation이라고 말할 수 있는데, 그림 13.2를 봐 봅시다. p라는 문제의 인풋인 x가 들어갔을 때 Transformation function T를 만나게 됩니다. 이 아웃풋인 T(x)는 다시 Q의 인풋이 되게되고,
이때 Transformation funcition은 P의 인풋을 Q의 인풋으로 바꿔주는 역할을 합니다.
다시 P 라는 문제를 Q라는 문제로 바꾸어서 Q 문제를 해결(그림에선 yes)하게 된다면 P의 문제도 해결(yes)하게 됩니다. 반대로 Q라는 문제로 바꾸어서 해결하지 못했을 때(no) P라는 문제도 해결하지 못하게 됩니다.
즉 우리는 Q를 해결하려는 알고리즘으로 P의 문제를 푼것이니, Q 문제가 더 어렵거나 같은 수준으로 어렵다고 할 수 있습니다.
위와같은 상황을 "Problem P is reducible to Q" 라고 말할 수 있습니다.
NP hard의 정의를 다시한번 봐봅시다. NP class에 있는 모든 문제가 어떤문제 Q로 reducible 하다면, 그 문제는 NP Hard 이다.
그럼 다시 NP complete문제로 돌아가 봅시다.
NP class에 속해있으면서 NP hard이면 NP complete 문제라고 합니다.
알고리즘으로 돌아가기
Algorithm
메인으로 돌아아기
P Class
정의.
Definition 13.3 The Class P
P is the class of decision problems that are polynomially bounded.
P is the class of decision problems that are polynomially bounded.
Definition 13.2 Polynomially bounded
An algorithm is said to be polynomially Bounded if its worst-case complexity is bounded by a polynomial function of the input size.
A problem is said to be polynomially bounded if there is a polynomially bounded algorithm for it.
An algorithm is said to be polynomially Bounded if its worst-case complexity is bounded by a polynomial function of the input size.
A problem is said to be polynomially bounded if there is a polynomially bounded algorithm for it.
간단하게 말해 어떤 문제에 대해 polynomially time algorithm이 존재할 때, 그 문제는 P Class에 속한다고 할 수 있습니다. 이때 알고리즘이 P class가 아닌 문제가 P class에 속하는 것 입니다.
polynomially time algorithm(다항 시간 알고리즘) 이란 Worst-case에서의 시간복잡도가 N^a 으로 정의 되는 것을 말합니다. (단, a는 상수)
우리가 지금까지 배운 알고리즘은 모두 O(n^a)으로 정의할 수 있으니 그와 관련된 문제는 P class에 속한다고 할 수 있습니다.
P class의 polynomially time algorithm 은 다른말로 Deterministic Polynomially time의 알고리즘이라고 할 수 있습니다. 이는 추후에 나올 NP class와 비교하면 그 이유를 알 수 있습니다.
NP Class
정의.
Definition 13.5 The class NP
NP is the class decision problems for which there is a polynomially bounded nondeterministic algorithm. (NP: Nondeterministic Polynomially Bounded.)
NP is the class decision problems for which there is a polynomially bounded nondeterministic algorithm. (NP: Nondeterministic Polynomially Bounded.)
Definition 13.4 Nondeterministic algorithm
A nondeterministic algorithm has two phases and an output step:
1. Nondeterministic "guessing" Phase:
Arbitrary string of characters, s, is written. (A solution is proposed.)
2. Deterministic "verifying" Phase:
Read the decision problem's input and optionally s.
Returns a value true or false, or it may get in an infinite loop.
3. Output step:
If the verifying phase returned true, the algorithm outputs yes.
Otherwise, there is no output.
A nondeterministic algorithm has two phases and an output step:
1. Nondeterministic "guessing" Phase:
Arbitrary string of characters, s, is written. (A solution is proposed.)
2. Deterministic "verifying" Phase:
Read the decision problem's input and optionally s.
Returns a value true or false, or it may get in an infinite loop.
3. Output step:
If the verifying phase returned true, the algorithm outputs yes.
Otherwise, there is no output.
이론.
Theorem 13.1
Previous sample problems are all in NP
Previous sample problems are all in NP
Theorem 13.2
P \subseteq NP.
P \subseteq NP.
proof.
A deterministic algorithm is a special case if a nondeterministic algorithm (executing only the second phase.)
NP class 는 간단하게 말하면 그 문제를 해결하는 nondeterministic polynomially time algorithm 이 존재한다면, 그 문제는 NP class에 속한다고 할 수 있습니다.
p class 의 정의와 비슷하지만 Nondeterministic이라는 단어가 이해되지 않을 수 있습니다.
Nondeterministic 은 "비결정론적"이라는 뜻인데, 비결정론적 알고리즘은 같은 입력을 주더라도 매번 다른 과정을 거쳐 다른 결과를 도출하는 알고리즘을 말합니다.
Nondeterministic 은 "비결정론적"이라는 뜻인데, 비결정론적 알고리즘은 같은 입력을 주더라도 매번 다른 과정을 거쳐 다른 결과를 도출하는 알고리즘을 말합니다.
그렇다면 결정론적 알고리즘은 예측한 그대로 동작하는 알고리즘이다. 같은 입력을 넣었을 때 매번 같은 과정을 거쳐 같은 결과를 도출하는 알고리즘을 뜻합니다.
이론 13.2에 의하면 P는 NP에 부분집합이거나 같습니다. P class에 문제가 NP에 모두 속한다는 뜻입니다.
NP Hard & NP Complete
정의.
Definition 13.7 NP-hard and NP-complete
A problem Q is NP hard if every problem P in NP is reducible to Q; that is, P \le {_PQ}. A problem Q is NP-Complete if it is in NP and NP-hard.
- Being NP-hard constitutes a lower bound on the problem.
- Being in NP constitutes an upper bound.
A problem Q is NP hard if every problem P in NP is reducible to Q; that is, P \le {_PQ}. A problem Q is NP-Complete if it is in NP and NP-hard.
- Being NP-hard constitutes a lower bound on the problem.
- Being in NP constitutes an upper bound.
Definition 13.6 Polynomial reduction and reducibility
Let T be a function from the input set for a decision problem P into the input set for a decision problem Q. T is a polynomial reduction (also called a polynomially transformation) from P to Q if all of the following hold:
1. T can be computed in polynomially bounded time.
2. For every string x, if x is a yes input for P, then T(x) is a yes input for Q.
3. For every string x, if x is a no input for P, then T(x) is a no input for Q.
it is usually easier to prove the contrapositive of part 3.
3'. For every x, if T(x) is a yes input for Q, then x, is a yes input for P.
problem P is polynomially reducible (also called polynomially transformable) to Q if there exists a polynomially transformation from P to Q. (We usually just say P is reducible to Q)
The notation
P \le {_pQ}
is used to indicate that P is reducible to Q.
P \le {_pQ} \iff Q is at least as hard to solve as P.
Let T be a function from the input set for a decision problem P into the input set for a decision problem Q. T is a polynomial reduction (also called a polynomially transformation) from P to Q if all of the following hold:
1. T can be computed in polynomially bounded time.
2. For every string x, if x is a yes input for P, then T(x) is a yes input for Q.
3. For every string x, if x is a no input for P, then T(x) is a no input for Q.
it is usually easier to prove the contrapositive of part 3.
3'. For every x, if T(x) is a yes input for Q, then x, is a yes input for P.
problem P is polynomially reducible (also called polynomially transformable) to Q if there exists a polynomially transformation from P to Q. (We usually just say P is reducible to Q)
The notation
P \le {_pQ}
is used to indicate that P is reducible to Q.
P \le {_pQ} \iff Q is at least as hard to solve as P.
Theorem 13.3
If P \le {_pQ} and Q is in P, then P is in P.
If P \le {_pQ} and Q is in P, then P is in P.
Theorem 13.4
If any NP-complete problem is in P, them P = NP.
How valuable it would be to find a polynomially bounded algorithm for any NP-complete problem.
How unlikely it is that such an algorithm exists because there are so many problems in NP for which polynomially bounded algorithms have been sought without success.
If any NP-complete problem is in P, them P = NP.
How valuable it would be to find a polynomially bounded algorithm for any NP-complete problem.
How unlikely it is that such an algorithm exists because there are so many problems in NP for which polynomially bounded algorithms have been sought without success.
정의가 엄청 길어 어려워보이지만 간단하게 말하면 NP complete problem 은 NP class 와 NP Hard, 두가지 조건을 충족해야한다는 것입니다. 그렇다면 NP complete problem을 아려면 NP hard에 대해서 알아야겠죠.
NP hard는 NP class에 있는 모든 문제가 어떤 문제 Q로 Reducible 하다면, 그문제 Q는 NP hard 이다고 말합니다.
NP hard는 NP class에 있는 모든 문제가 어떤 문제 Q로 Reducible 하다면, 그문제 Q는 NP hard 이다고 말합니다.
우리는 polynomial Reduction을 polynomially transformation이라고 말할 수 있는데, 그림 13.2를 봐 봅시다. p라는 문제의 인풋인 x가 들어갔을 때 Transformation function T를 만나게 됩니다. 이 아웃풋인 T(x)는 다시 Q의 인풋이 되게되고,
이때 Transformation funcition은 P의 인풋을 Q의 인풋으로 바꿔주는 역할을 합니다.
다시 P 라는 문제를 Q라는 문제로 바꾸어서 Q 문제를 해결(그림에선 yes)하게 된다면 P의 문제도 해결(yes)하게 됩니다. 반대로 Q라는 문제로 바꾸어서 해결하지 못했을 때(no) P라는 문제도 해결하지 못하게 됩니다.
즉 우리는 Q를 해결하려는 알고리즘으로 P의 문제를 푼것이니, Q 문제가 더 어렵거나 같은 수준으로 어렵다고 할 수 있습니다.
위와같은 상황을 "Problem P is reducible to Q" 라고 말할 수 있습니다.
NP hard의 정의를 다시한번 봐봅시다. NP class에 있는 모든 문제가 어떤문제 Q로 reducible 하다면, 그 문제는 NP Hard 이다.
그럼 다시 NP complete문제로 돌아가 봅시다.
NP class에 속해있으면서 NP hard이면 NP complete 문제라고 합니다.
알고리즘으로 돌아가기
Algorithm
메인으로 돌아아기
P Class
정의.
Definition 13.3 The Class P
P is the class of decision problems that are polynomially bounded.
P is the class of decision problems that are polynomially bounded.
Definition 13.2 Polynomially bounded
An algorithm is said to be polynomially Bounded if its worst-case complexity is bounded by a polynomial function of the input size.
A problem is said to be polynomially bounded if there is a polynomially bounded algorithm for it.
An algorithm is said to be polynomially Bounded if its worst-case complexity is bounded by a polynomial function of the input size.
A problem is said to be polynomially bounded if there is a polynomially bounded algorithm for it.
간단하게 말해 어떤 문제에 대해 polynomially time algorithm이 존재할 때, 그 문제는 P Class에 속한다고 할 수 있습니다. 이때 알고리즘이 P class가 아닌 문제가 P class에 속하는 것 입니다.