맨위로가기

NP-난해

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
목차

1. 개요

NP-난해는 계산 복잡도 이론에서 중요한 개념으로, 어떤 문제가 NP에 속하는 모든 문제를 다항 시간 안에 풀 수 있다면 해당 문제는 NP-난해라고 정의된다. NP-난해 문제는 결정 문제뿐만 아니라 탐색 문제, 최적화 문제 등 다양한 문제들을 포함하며, 다항 시간 다대일 환원 또는 튜링 환산을 통해 정의될 수 있다. 만약 P ≠ NP라면, NP-난해 문제는 다항 시간 내에 해결될 수 없으며, NP-완전 문제와 밀접한 관련을 가진다. 부분집합 합 문제, 정지 문제, 외판원 문제 등이 NP-난해 문제의 예시이며, 근사 계산, 암호학, 데이터 마이닝 등 다양한 분야에서 응용된다.

더 읽어볼만한 페이지

  • NP-난해 문제 - 외판원 문제
    외판원 문제(TSP)는 여러 도시를 모두 한 번씩 방문하고 출발점으로 돌아오는 최소 비용의 이동 순서를 구하는 문제로, NP-난해 문제에 속하며, 배송 계획 등에 응용되고 다양한 해법이 존재한다.
  • 복잡도 종류 - P (복잡도)
    P는 결정론적 튜링 기계로 다항 시간 내에 풀 수 있는 판정 문제들의 집합이며, 다항 시간 균일 불 대수 회로 집합으로도 정의되고, NP, co-NP 등 다른 복잡도 종류들과 관계를 가진다.
  • 복잡도 종류 - P-NP 문제
    P-NP 문제는 계산 복잡도 이론에서 P와 NP 복잡도 종류의 관계에 대한 미해결 문제로, 컴퓨터 과학과 수학에 혁명적인 변화를 가져올 것으로 예상되며 암호학, 최적화, 인공지능 등 다양한 분야에 큰 영향을 미칠 수 있다.
NP-난해
개요
정의어떤 문제 L이 NP-난해이다는 것은, L이 NP에 속하든 속하지 않든, NP에 속하는 모든 문제들이 다항 시간 안에 L로 환원될 수 있다는 의미이다.
설명NP-난해 문제는 NP에 속하는 모든 문제만큼 어렵다는 것을 의미하며, NP-난해 문제 자체가 NP에 속할 필요는 없다.
예시정지 문제
충족 가능성 문제
외판원 문제
NP, NP-완전, NP-난해 관계
P, NP, NP-완전 집합 간의 관계를 나타내는 오일러 다이어그램
P, NP, NP-완전 집합 간의 관계를 나타내는 오일러 다이어그램. P=NP일 경우, 다이어그램의 모든 집합은 같아진다.
NPNP-난해는 NP에 속할 필요가 없다. 어떤 문제가 NP-난해이면서 NP에 속하면, 그 문제는 NP-완전이다.
NP-완전만약 NP에 속하는 어떤 문제가 다항 시간 안에 풀릴 수 있다면, NP에 속하는 모든 문제들은 다항 시간 안에 풀릴 수 있다. 왜냐하면 NP에 속하는 모든 문제들은 정의에 따라 NP-완전 문제로 다항 시간 안에 환원될 수 있기 때문이다.
NP-난해 문제의 예
정지 문제정지 문제는 어떤 프로그램과 입력이 주어졌을 때, 그 프로그램이 입력을 처리하는 동안 멈출지 무한 루프에 빠질지를 결정하는 문제이다. 앨런 튜링이 증명했듯이, 정지 문제는 풀 수 없는 문제이다.
충족 가능성 문제충족 가능성 문제는 주어진 부울 대수식이 참이 되는 변수 할당이 존재하는지 여부를 결정하는 문제이다. 이 문제는 NP-완전 문제의 대표적인 예시이며, 많은 다른 NP-완전 문제들이 충족 가능성 문제로 환원될 수 있다.
외판원 문제외판원 문제는 주어진 도시들의 목록과 각 도시 사이의 거리가 주어졌을 때, 모든 도시를 정확히 한 번씩 방문하고 시작 도시로 돌아오는 최단 경로를 찾는 문제이다. 이 문제는 NP-난해 문제이며, 최적 해를 찾는 것은 매우 어렵다.
참고 문헌

2. 정의

NP-난해는 수학적으로 다음과 같이 정의한다.

: 언어 L이 모든 L^\prime\in \mathbf{NP}에 대해 L^\prime \leq_p L\!을 만족하면, L은 '''NP-난해'''이다.

NP-난해의 정의에서 다항 시간 다대일 환산을 다항 시간 튜링 환산으로 정의하는 경우도 있다. 이 정의가 앞의 정의와 같은지 다른지는 아직 해결되지 않은 문제이다. 튜링 환산 방식은 함수 문제에 대해서도 형식화할 수 있다는 장점이 있다.

2. 1. 다항 시간 환원

결정 문제 ''H''가 NP-난해라는 것은, NP에 속하는 모든 문제 ''L''에 대해, ''L''에서 ''H''로의 다항 시간 다대일 환원이 존재한다는 것을 의미한다.[1]

다른 정의로는 NP-완전 문제 ''G''에서 ''H''로의 다항 시간 환원이 존재하는 경우가 있다.[1] NP에 속하는 모든 문제 ''L''은 다항 시간 안에 ''G''로 환원되므로, ''L''은 다시 다항 시간 안에 ''H''로 환원된다. 이 새로운 정의는 이전 정의를 포함한다. 이는 NP-난해 범위를 결정 문제로 제한하지 않으며, 탐색 문제 또는 최적화 문제도 포함한다.

2. 2. 튜링 환산

어떤 문제 L이 NP-난해라는 것은, L에 대한 신탁 기계를 사용하여 NP에 속하는 모든 판정 문제를 다항 시간 안에 풀 수 있다는 의미이다. 즉, L을 푸는 함수가 단위 시간만 걸린다고 가정할 때, NP에 속하는 모든 문제를 다항 시간 안에 풀 수 있다는 것이다.[1]

3. P ≠ NP 문제와의 관계

P ≠ NP이면 NP-난해 문제는 다항 시간 내에 해결될 수 없다.[6]

일부 NP-난해 최적화 문제는 일부 상수 근사율(특히 APX)까지 또는 임의의 근사율(PTAS 또는 FPTAS)까지 다항 시간 근사 알고리즘으로 근사될 수 있다. 각기 다른 수준의 근사를 가능하게 하는 많은 근사 가능성 클래스가 있다.[6]

만약 어떤 NP-난해 문제를 다항 시간 내에 푸는 알고리즘이 존재한다면, NP의 모든 문제에 대해 다항 시간 내에 풀 수 있게 되어 P = NP가 성립한다. 하지만 P=NP가 성립해도 "'''임의의''' NP-난해 문제를 다항 시간 내에 풀 수 있다"고는 말할 수 없다.

4. 예제

NP-난해 문제의 예시는 다음과 같다.


  • 모든 NP-완전 문제는 NP-난해 문제이다. 예를 들어, 외판원 문제는 주어진 가중 그래프의 모든 노드를 통과하는 최소 비용 순환 경로를 찾는 최적화 문제로, NP-난해 문제이다.[7]
  • 정지 문제는 "한 프로그램과 그 프로그램에 대한 입력이 있을 때, 이 프로그램은 영원히 돌 것인가?" 하는 문제이다. 충족 가능성 문제를 정지 문제로 환산하는 것으로 보일 수 있는데, 이때 정지 문제의 입력으로 받는 튜링 기계는 입력으로 받은 식에 대해서 식을 만족하는 진리값을 발견할 때에만 멈추고 그렇지 않으면 무한 루프에 빠지도록 설계하면 된다. 정지 문제는 NP에 속하지 않는데, 이것은 NP 문제는 유한 번의 연산으로 판정이 가능하지만 정지 문제는 그렇지 않기 때문이다.
  • NP-난해하지만 ''NP-완전''도 아니고 ''결정 불가능''하지도 않은 문제도 있다. 예를 들어, 참 정량화 부울 식의 언어는 다항 공간에서 결정 가능하지만, 비결정적 다항 시간 내에서는 결정 불가능하다(NP = PSPACE가 아닌 한).[8]

4. 1. 결정 문제

부분집합 합 문제는 주어진 정수 집합에서 원소의 합이 0이 되는 공집합이 아닌 부분집합이 존재하는지 판별하는 문제이다.[7] 정지 문제는 주어진 프로그램과 입력에 대해 해당 프로그램이 영원히 실행될지 아니면 멈출지 판별하는 문제인데, NP-난해이지만 NP-완전은 아니다.[7] 해밀턴 회로 문제는 주어진 그래프에서 모든 정점을 한 번씩만 방문하고 출발점으로 돌아오는 경로(해밀턴 회로)가 존재하는지 판별하는 문제이다.[8] 충족 가능성 문제는 주어진 논리식이 참이 되도록 하는 변수 할당이 존재하는지 판별하는 문제로, 정지 문제로 환산하여 보일 수 있다.[7]

4. 2. 조합 최적화 문제

외판원 문제는 주어진 모든 도시를 한 번씩 방문하고 출발점으로 돌아오는 최단 경로를 찾는 문제이다. 이 문제는 대표적인 NP-난해 문제로, 대한민국 물류 산업 등 다양한 분야에서 효율적인 경로 설계를 위해 연구되고 있다.[7]

배낭 문제는 주어진 배낭 용량과 각 아이템의 가치, 무게가 있을 때, 배낭에 담을 수 있는 아이템들의 최대 가치를 구하는 문제이다.

최소 정점 덮개 문제는 주어진 그래프에서 모든 간선(edge)을 포함하는 최소 크기의 정점(vertex) 집합을 찾는 문제이다.

최대 독립 집합 문제는 주어진 그래프에서 서로 인접하지 않은 정점들의 최대 크기 집합을 찾는 문제이다.

5. NP 관련 용어

계산 복잡도에서 핵심적인 역할을 하는 NP를 기반으로 여러 용어들이 사용된다.


  • '''NP''': 주어진 '예' 해답이 결정적 튜링 머신으로 다항 시간 안에 해답으로 검증될 수 있는 (또는 '비결정적' 튜링 머신으로 다항 시간 안에 '풀릴 수 있는') 계산 결정 문제의 종류이다.
  • '''NP-난해''': NP에서 가장 어려운 문제만큼 어려운 문제의 종류이다. NP-난해 문제는 NP의 요소일 필요는 없으며, 실제로 결정 불가능할 수도 있다.
  • '''NP-중간''': P와 NP가 다르다면, P와 NP-완전 문제 사이에 속하는 NP 영역에 결정 문제가 존재한다. (P와 NP가 같은 종류라면, 모든 NP-완전 문제가 P에 속하고, 정의상 NP의 모든 문제는 NP-완전 문제로 환원될 수 있으므로 NP-중간 문제는 존재하지 않는다.)


"NP-난해"라는 명칭은 "NP"가 붙지만, 모두가 NP인 것은 아니다. 하지만 현재 상황에서는 정착된 명칭이므로, 바뀌지는 않을 것이다.

5. 1. NP-완전 (NP-complete)

NP-완전은 NP에 속하면서 동시에 NP-난해인 문제들을 의미한다. 즉, NP-완전 문제는 NP에서 가장 어려운 문제들이다.

NP-완전은 NP에서 가장 어려운 문제를 포함하는 결정 문제의 종류이며, 각 NP-완전 문제는 NP에 속해야 한다.

NP-완전이라는 명칭은 NP의 '''중에서''' "완전"한 문제를 의미한다. 다시 말해, NP의 '''중에서''' 가장 풀기 어렵다는 것을 뜻한다.

5. 2. NP-쉬움 (NP-easy)

NP-쉬움은 "기껏해야" NP와 동등 이하로 어렵지 않은 문제 (단, NP'''에 속하는''' 것은 아니다). NP보다 기껏해야 어렵지만, 반드시 NP에 속할 필요는 없다.[1]

5. 3. NP-동등 (NP-equivalent)

NP-동등은 NP-난해이면서 NP-쉬움인 결정 문제이나, 반드시 NP에 속할 필요는 없다.

용어설명
NP-완전NP 중에서 "완전"한 문제로, NP 중에서 가장 풀기 어렵다.
NP-난해"최소한" NP와 동등 이상으로 어려운 문제 (단, NP에 속하는 것은 아님).
NP-쉬움"기껏해야" NP와 동등 이하로 어렵지 않은 문제 (단, NP에 속하는 것은 아님).
NP-동등NP와 동등하게 어려운 문제 (단, NP에 속하는 것은 아님).




6. 응용 분야

P ≠ NP이면 NP-난해 문제는 다항 시간 내에 해결될 수 없다.

일부 NP-난해 최적화 문제는 일부 상수 근사율(APX)까지 또는 임의의 근사율(PTAS 또는 FPTAS)까지 다항 시간 근사 알고리즘으로 근사될 수 있다. 각기 다른 수준의 근사를 가능하게 하는 많은 근사 가능성 클래스가 있다.[6]

NP-난해 문제는 다음과 같은 분야에서 규칙 기반 언어로 해결되는 경우가 많다.

참조

[1] 서적 Handbook of Theoretical Computer Science Elsevier
[2] 간행물 Postscript about NP-hard problems 1974
[3] 서적 Introduction to the Theory of Complexity Prentice Hall
[4] 웹사이트 Shtetl-Optimized » Blog Archive » The Scientific Case for P≠NP http://www.scottaaro[...] 2016-09-25
[5] 웹사이트 Is undecidable(complement of R) a subset of NP-hard? https://cs.stackexch[...] 2024-02-09
[6] 간행물 A survey on the structure of approximation classes
[7] 서적 The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization https://archive.org/[...] John Wiley & Sons
[8] 서적 Complexity Theory: Exploring the Limits of Efficient Algorithms https://books.google[...] Springer
[9] 서적 組合せ最適化 第2版 (理論とアルゴリズム) 丸善


본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com