NP-Completeness - 편집 역사

Ahn9807: 봇: 자동으로 텍스트 교체 (-\[\[분류:컴퓨터 공학(\|[^\]]+)?\]\] +)

2026-01-15T15:23:05Z

봇: 자동으로 텍스트 교체 (-\[\[분류:컴퓨터 공학(\|[^\]]+)?\]\] +)

← 이전 판		2026년 1월 15일 (목) 15:23 판
1번째 줄:		1번째 줄:
	[[분류:알고리즘 설계와 분석]]		[[분류:알고리즘 설계와 분석]]
	~~[[분류:컴퓨터 공학]]~~
	상위 문서: [[알고리즘 설계와 분석#NP-Completeness\|알고리즘 설계와 분석]]		상위 문서: [[알고리즘 설계와 분석#NP-Completeness\|알고리즘 설계와 분석]]

Pinkgo: /* Reduction */

2025-12-01T16:39:16Z

Reduction

← 이전 판		2025년 12월 1일 (월) 16:39 판
32번째 줄:		32번째 줄:
	A → B이면 A<math>\le</math>p B 이며, B는 A보다 더 빨라질 수 없다.		A → B이면 A<math>\le</math>p B 이며, B는 A보다 더 빨라질 수 없다.
	이는 hardness 관점에서 A가 다항시간에 해결되지 않는 문제라고 할 때, B가 다항시간 내에 해결된다면 A 또한 다항 시간 내에 해결될 수 있기 때문이다. 따라서 주어진 문제 B가 다항시간에 해결되지 않는 것을 증명하기 위해서는 이미 다항시간 내에 해결될 수 없다는 것이 증명된 문제 A를 B로 A → B와 같이 reduction하여 해결할 수 있다.		이는 hardness 관점에서 A가 다항시간에 해결되지 않는 문제라고 할 때, B가 다항시간 내에 해결된다면 A 또한 다항 시간 내에 해결될 수 있기 때문이다. 따라서 주어진 문제 B가 다항시간에 해결되지 않는 것을 증명하기 위해서는 이미 다항시간 내에 해결될 수 없다는 것이 증명된 문제 A를 B로 A → B와 같이 reduction하여 해결할 수 있다.

			==[[Satisfiability Problem]]==
			SAT(Satisfiability Problem)는 컴퓨터 과학 이론에서 가장 유명한 NP-complete 문제이며, 전 세계의 알고리즘 전문가들이 빠른 알고리즘(다항시간)을 찾으려 했지만 실패했다. SAT를 빠르게 풀 수 있으면 P = NP가 되어버리며, NP 문제들이 전부 빠르게 풀려 암호 시스템 대부분이 붕괴한다.

			[[Satisfiability Problem\|SAT]]에 대한 자세한 내용은 해당 문서를 참조해 주십시오.

	==각주==		==각주==

Pinkgo: /* 개요 */

2025-11-24T06:39:42Z

개요

← 이전 판		2025년 11월 24일 (월) 06:39 판
10번째 줄:		10번째 줄:
	사실 어떤 문제를 해결하고자 할때, 이를 풀기 위한 다항시간 알고리즘을 찾을 수 없는 경우가 있다. 하지만 exponential-time lower bound 증명은 현재 기술로 거의 불가능하므로 이러한 문제들이 “진짜로 어려운지” 증명할 방법이 없었다. 하지만 Stephen Cook과 Richard Karp는 “어떤 문제가 다른 어려운 문제와 본질적으로 동일한 난이도를 가진다”는 개념을 만들었고, 이것이 바로 NP-completeness이다.		사실 어떤 문제를 해결하고자 할때, 이를 풀기 위한 다항시간 알고리즘을 찾을 수 없는 경우가 있다. 하지만 exponential-time lower bound 증명은 현재 기술로 거의 불가능하므로 이러한 문제들이 “진짜로 어려운지” 증명할 방법이 없었다. 하지만 Stephen Cook과 Richard Karp는 “어떤 문제가 다른 어려운 문제와 본질적으로 동일한 난이도를 가진다”는 개념을 만들었고, 이것이 바로 NP-completeness이다.

	~~앞으로~~ NP-Completeness에 대해서 ~~알아보기 전에,~~ 먼저 문제(problem)가 무엇인지 정의해야 한다. 문제란 일반화된 질문(general question)으로서, 아래의 두 요소로 이루어져 있다:		==Problems==
			NP-Completeness에 대해서 서술하기 위해서는 먼저 문제(problem)가 무엇인지 정의해야 한다. 문제란 일반화된 질문(general question)으로서, 아래의 두 요소로 이루어져 있다:
	# 입력의 종류와 제약(Parameters of the input)		# 입력의 종류와 제약(Parameters of the input)
	# 무엇이 “정답”인지 조건을 명시한 것(conditions on a satisfactory answer)		# 무엇이 “정답”인지 조건을 명시한 것(conditions on a satisfactory answer)

Pinkgo: /* 개요 */

2025-11-24T06:39:12Z

개요

← 이전 판		2025년 11월 24일 (월) 06:39 판
9번째 줄:		9번째 줄:
	# 내 잘못이 아니라, 세상의 그 누구도 풀 수 없는 문제다. → 간단함.		# 내 잘못이 아니라, 세상의 그 누구도 풀 수 없는 문제다. → 간단함.
	사실 어떤 문제를 해결하고자 할때, 이를 풀기 위한 다항시간 알고리즘을 찾을 수 없는 경우가 있다. 하지만 exponential-time lower bound 증명은 현재 기술로 거의 불가능하므로 이러한 문제들이 “진짜로 어려운지” 증명할 방법이 없었다. 하지만 Stephen Cook과 Richard Karp는 “어떤 문제가 다른 어려운 문제와 본질적으로 동일한 난이도를 가진다”는 개념을 만들었고, 이것이 바로 NP-completeness이다.		사실 어떤 문제를 해결하고자 할때, 이를 풀기 위한 다항시간 알고리즘을 찾을 수 없는 경우가 있다. 하지만 exponential-time lower bound 증명은 현재 기술로 거의 불가능하므로 이러한 문제들이 “진짜로 어려운지” 증명할 방법이 없었다. 하지만 Stephen Cook과 Richard Karp는 “어떤 문제가 다른 어려운 문제와 본질적으로 동일한 난이도를 가진다”는 개념을 만들었고, 이것이 바로 NP-completeness이다.

			앞으로 NP-Completeness에 대해서 알아보기 전에, 먼저 문제(problem)가 무엇인지 정의해야 한다. 문제란 일반화된 질문(general question)으로서, 아래의 두 요소로 이루어져 있다:
			# 입력의 종류와 제약(Parameters of the input)
			# 무엇이 “정답”인지 조건을 명시한 것(conditions on a satisfactory answer)
			즉, 입력과 출력의 조건을 정의한 것이 '문제'이다. 또한 인스턴스(instance)는 해당 문제의 구체적인 입력을 의미한다. 더 쉽게 말하면, 특정 입력값으로 완전히 명시된 문제이다. 예를 들어, 정렬 문제는 아래와 같은 입력과 출력을 가진다:
			입력: <math>a_1, ..., a_n</math>으로 이루어진 수열
			출력: 해당 수열을 재배열하여 <math> a'_1 \le a'_2 \le ... \le a'_n</math>이 되도록 하는 것
			이 경우, 인스턴스는 {3,5,2,7,4,8,1}과 같이 구체적으로 제시된 특정 순열이다. 또한 결정 문제(Decision Problems)는 답이 “예/아니오(yes/no)”로만 나오는 문제이다. 예를 들어 [[Minimum Spanning Trees\|MST]] 문제는 출력이 "예/아니오"로 정의되지 않으므로 정렬 문제가 아니지만, "주어진 그래프 G와 정수 k에 대해 비용이 k 이하인 MST가 존재하는가?"는 결정 문제에 해당한다.<br>
			이때 NP-Completeness는 결정 문제에 대해 주로 적용되므로, 해당 문서에서의 모든 문제들은 결정 문제 형식으로 통일하여 다룬다.

	==Reduction==		==Reduction==

2025년 11월 24일 (월) 06:16에 Pinkgo님의 편집

2025-11-24T06:16:09Z

@@ 1번째 줄: / 1번째 줄: @@
 [[분류:알고리즘 설계와 분석]]
 [[분류:컴퓨터 공학]]
-상위 문서: [[알고리즘 설계와 분석#문제|알고리즘 설계와 분석]]
+상위 문서: [[알고리즘 설계와 분석#NP-Completeness|알고리즘 설계와 분석]]
 ==개요==

Pinkgo: 새 문서: 분류:알고리즘 설계와 분석 분류:컴퓨터 공학 상위 문서: 알고리즘 설계와 분석 ==개요==

2025-11-24T05:14:00Z

새 문서: 분류:알고리즘 설계와 분석 분류:컴퓨터 공학 상위 문서: 알고리즘 설계와 분석 ==개요==

새 문서

[[분류:알고리즘 설계와 분석]]
[[분류:컴퓨터 공학]]
상위 문서: [[알고리즘 설계와 분석#문제|알고리즘 설계와 분석]]

==개요==