algo_lec12

Today's Topics

• Realistic / Unrealistic algorithms
• Tractable / Intractable problems
• Non-deterministic algorithms
    - Polynomial-time non-deterministic algorithms
• P, NP
• NP examples

---

Realistic Algorithms

An algorithm is considered "realistic" if its execution cost grows polynomially with respect to the input size.

입력 크기 nnn에 대해 실행 비용(수행 시간)이 다항 시간(Polynomial Time) 내에서 증가하는 알고리즘

Examples of polynomial time complexities: O(n²), O(n³.⁵), O(n¹⁰⁰)

O(n²), O(n³.⁵), O(n¹⁰⁰) 등
→ 입력 크기가 커질수록 실행 시간이 증가하긴 하지만, 그 성장이 기하급수적으로 빠르지 않고, 점진적으로 증가.

These are manageable because computer performance improves over time (e.g., doubles every two years).

 

• 컴퓨터 성능은 지속적으로 발전하고 있고,
  (예: 약 2년마다 처리 속도가 2배가 됨 — 무어의 법칙)
• 다항 시간 알고리즘은 이런 성능 향상으로 충분히 해결 가능한 범위 내에 있음

The class P consists of all problems that can be solved in polynomial time, thus at a realistic cost.

 

• P(Class P): 입력에 대해 다항 시간 내에 해결 가능한 문제들의 집합
• 즉, 현실적으로 풀 수 있는 문제들이라고 볼 수 있습니다.

---

 

 

Unrealistic Algorithms

Algorithms with exponential time complexities, 

실행 시간이 지수 함수적으로 증가하는 알고리즘

 

such as O(2ⁿ), O(2.5ⁿ), O(100ⁿ), are considered unrealistic.

입력 크기 nnn이 조금만 커져도 실행 시간이 폭발적으로 증가.

Even small inputs lead to astronomical running times, beyond what is feasible with any computing power.

입력 값이 조금만 커져도 계산 불가능한 수준의 시간이 걸림

---

Efficiency vs Difficulty

Efficiency: Is the algorithm practically fast? Only low-degree polynomial algorithms are truly efficient.

 

• 알고리즘이 실제로 빠르게 동작하는가?
• 이 질문은 단순히 시간 복잡도가 다항식(Polynomial) 이냐가 아니라,
  그 다항식의 차수가 얼마나 낮은가에 따라 달라집니다.
• 따라서, 낮은 차수의 다항 시간 알고리즘만이 진짜 효율적

Difficulty: Are there fundamental limits preventing a problem from being solved efficiently?

• 근본적으로 이 문제는 효율적으로 풀 수 없는 구조인가?
• 다시 말해, 현재까지 어떤 알고리즘도 이 문제를 다항 시간 내에 해결하지 못하고 있다면,
  이 문제는 본질적으로 어려운 문제라고 판단.
• 이런 문제들은 보통 NP-hard 또는 NP-complete 문제로 분류됨.

---

 

Tractable / Intractable Problems

( 다룰 수 있는 문제 vs 다루기 어려운 문제 )

A problem is tractable if it can be solved in polynomial time (Θ(n^k)).

• 다항 시간 내에 해결할 수 있는 문제를 의미.
• 즉, 문제의 입력 크기를 nnn이라고 했을 때, 해결 시간 또는 계산량이 Θ(nk) 수준인 문제.

예시:

• 정렬 알고리즘: O(n log n)
• 최단 경로 문제 (Dijkstra, Floyd-Warshall 등)

→ 현실적으로 풀 수 있는 문제들입니다.
→ P 클래스에 속하는 문제들이 여기에 해당됩니다.

A problem is intractable if no known polynomial time algorithm exists (e.g., Θ(2^k), Θ(n!)).

• 현재까지 다항 시간 알고리즘이 알려지지 않은 문제.
• 즉, 알고 있는 알고리즘들이 Θ(2k), Θ(n!) 같은 지수적 또는 팩토리얼 복잡도를 가질 때.

예시:

• 0-1 Knapsack 문제 (완전 탐색 시 O(2^n))
• 외판원 문제(TSP: Travelling Salesman Problem)
• 그래프 색칠 문제(Graph Coloring)

→ 이론적으로는 계산 가능하지만, 현실에서는 너무 느려서 풀 수 없음

---

Deterministic vs Non-deterministic Algorithms

Deterministic algorithms always produce the same output for a given input.

• 항상 같은 입력에 대해 같은 출력을 내는 알고리즘.
• 내부 동작이 완전히 예측 가능하고 명확하게 정의되어 있음.

예시:

• 이진 탐색 알고리즘
• 선택 정렬, 합병 정렬 등

→ 매번 동일한 방식으로 계산되므로, 결과도 항상 동일.

 

Non-deterministic algorithms may 'guess' a solution and then verify it.

• 일종의 “추측”을 통해 해를 고르고, 그 해가 맞는지 검증하는 방식을 취하는 알고리즘.
• 마치 모든 가능성을 동시에 시도할 수 있는 초능력 머신을 상상한 것처럼 작동.

실제 의미:

• 이론적인 개념이며, 실제 컴퓨터가 구현할 수 있는 방식은 아님
• NP 문제들은 바로 이런 방식으로 “정답인지 아닌지를 빠르게 검증할 수 있는” 구조입니다.

예시:

• 그래프 색칠 문제에서:
  • “색칠을 먼저 해본다” (추측)
  • “서로 인접한 정점이 다른 색인지 확인” (검증)

---

Polynomial-time Non-deterministic Algorithms

(다항 시간 비결정적 알고리즘)

These algorithms guess a solution and verify it in polynomial time.

They do not necessarily find the optimal solution in polynomial time.

1. 정답이 무엇일지 "추측"한다.
2. 그 정답이 정말 맞는지 확인하는 과정은 다항 시간 내에 가능하다.

 

• 정답을 직접 계산해내는 게 아니라,
  마치 누군가가 "정답 후보"를 제시해주었다고 가정하고,
• 그것이 올바른 해인지 빠르게(다항 시간 내에) 검증만 하면 되는 구조입니다.

 

---

Definition of NP

NP is the set of decision problems solvable by non-deterministic algorithms in polynomial time.

비결정적 알고리즘으로 다항 시간 내에 풀 수 있는 결정 문제들의 집합
An optimization problem can often be transformed into a corresponding decision problem.

최적화 문제는 결정 문제로 바꿀 수 있음.

---

Optimization vs Decision Problem

Example - Graph Coloring:
• Optimization: Find the minimum number of colors to color the graph.

[최적화 문제] 그래프를 색칠할 때 필요한 최소 색 수를 구하라.
• Decision: Can the graph be colored with k or fewer colors?

[결정 문제] 주어진 그래프가 k개의 색으로 색칠 가능한가?

---

P vs NP

P ⊆ NP ⊆ Decision Problem. 

Every problem in P is also in NP.

 

Every problem that can be solved in polynomial time can also be verified in polynomial time.
It remains unknown whether P = NP. Most computer scientists believe P ≠ NP.

---

General Categories of Problems

(1) Problems with known polynomial-time algorithms (e.g., sorting)

• 다항 시간 알고리즘이 알려진 문제들

(2) Intractable problems (e.g., 0-1 knapsack)

• 다룰 수 없는 문제들 (비효율적 문제들)

(3) Undecidable problems (e.g., the halting problem)

• 판단 불가능한 문제들

---

How to Decide the given problem is in NP

Step 1: Reformulate as a decision problem.

결정 문제로 바꾸기 (Reformulate as a decision problem)

원래의 최적화 문제를 예/아니오로 답할 수 있는 결정 문제로 바꿈. NP는 결정 문제만 포함하므로, 이 과정이 필수.
[예시]
최적화 문제: 그래프를 최소한의 색으로 색칠하라.→ 결정 문제: 이 그래프를 4가지 색으로 색칠할 수 있는가? (Yes/No)

Step 2: Guess a solution.

해답을 "추측"하기 (Guess a solution)

비결정적 알고리즘이라고 생각하고, 어떤 정답 후보를 "마법처럼" 하나 고른다고 가정.
이 정답은 반드시 올바른 정답일 필요는 없지만, 검증 가능한 형태여야함.
[예시]
앞서 말한 색칠 문제라면, 각 정점에 특정 색을 할당한 배열을 ‘추측’했다고 가정.

 

Step 3: Check if the solution can be verified in polynomial time.

추측한 해답을 다항 시간 내에 검증할 수 있는지 확인 (Verify in polynomial time)

추측한 정답이 정말 맞는지 확인하는 데 걸리는 시간이 다항 시간 이내인지 확인.
이 검증이 빠르게 가능하다면, 그 문제는 NP에 속합니다.
[예시]
색칠 배열을 보고, 모든 인접한 정점이 다른 색인지 확인 → 간선 개수만큼 확인 → O(E) → 다항 시간 가능 → NP

---

NP Example 1: Searching

Problem: For the list s = [3, 9, 12, 5, 8, 10, 7], is there an element equal to 8?
이 리스트에 숫자 8이 존재하는가?

Decision version: Is there an element in the list that equals 8?

• 예(Yes) 또는 아니오(No)로 대답할 수 있는 형태.
• 결정 문제 조건 만족 → NP 문제로 표현 가능

Guessing stage: Guess an index i = 3

i = 3 이라고 추측하면 → s[3] = 5
→ s[3] ≠ 8 이므로 이 추측은 틀린 해답

 

Verification stage: Check if s[3] = 8. Since s[3] = 5 ≠ 8, output is NO.

추측한 인덱스의 값이 8인지 한 번 확인

This problem is in NP because verification (checking if a guessed index gives the target) is possible in constant/polynomial time.

검증은 다항 시간 내에 가능 → NP 조건 만족

---

NP Example 2: Traveling Salesman Problem (TSP)

Problem: Find a tour that visits each vertex exactly once with minimal total cost.
모든 도시(정점)를 정확히 한 번씩 방문하고, 다시 출발점으로 돌아오는 가장 짧은 경로를 찾는 문제

Decision version: Is there a tour of cost ≤ k?
모든 도시를 한 번씩 방문하고 되돌아오는 경로 중, 총 비용이 k 이하인 경로가 존재하는가? 

→ 예/아니오로 대답 가능 → 결정 문제 조건 만족

Guessing stage: Propose a vertex sequence (v1, v2, ..., vn).

비결정적 알고리즘은 해답(경로)을 먼저 추측한다고 가정

Verification stage: Add up the weights of the edges in the sequence and check if the total ≤ k.

1. 경로에 포함된 모든 간선이 실제 그래프에 존재하는지 확인
2. 모든 정점을 정확히 한 번씩 방문했는지 확인
3. 경로의 총 비용을 계산하고 k 이하인지 비교

The problem is in NP because we can verify the guessed tour cost in polynomial time.
→ 각 단계는 정점 수 n에 대해 O(n²) 이내로 가능
→ 검증은 다항 시간(polynomial time) 내에 가능

---

NP Example 3: Graph Coloring

Problem: What is the minimum number of colors needed to color a graph G?
그래프 G에 색깔이 최소 몇 개 필요?

Decision version: Can the graph G be colored using k or fewer colors?
k개 색깔을 이용하여 그래프 G를 칠할 수 있는가?

decision version으로 바꾸기 

Guessing stage: Assign colors to all vertices.
모든 정점에 색 할당

Verification stage: Check all adjacent pairs of vertices to ensure no two share the same color.
같은 색이 겹치지 않는지 검증

This can be verified in O(VE) time, so the problem is in NP.
→ 정점 수 V, 간선 수 E일 때,
→ 최대 E개의 인접 정점 쌍을 확인하므로,
→ 총 검증 시간: O(E)

 

∴ 검증은 다항 시간 내 가능 → NP 조건 만족

---

NP Example 4: Hamiltonian Cycle

Problem: Does graph G contain a Hamiltonian cycle (visiting all nodes once and returning to start)?
주어진 그래프 G가 있을 때, 모든 정점을 정확히 한 번씩 방문하고, 시작점으로 돌아오는 닫힌 경로(cycle) 가 존재하는가?

Decision version: Does such a cycle exist?

예 / 아니오로 대답할 수 있으므로, 결정 문제 조건 만족

Guessing stage: Propose a sequence of vertices forming a cycle.
비결정적 알고리즘이라고 가정하고, 정점들의 순서를 하나의 순열로 "추측"

Verification stage:

Check that each consecutive pair (and the last to first) are connected and all nodes are visited exactly once.

1. 모든 정점을 정확히 한 번씩 포함하고 있는가?
2. 각 정점 쌍이 실제 간선으로 연결되어 있는가?
   (예: v1과 v3 사이에 간선이 있어야 함)
3. 마지막 정점이 처음 정점으로 돌아오는가?
   (즉, 사이클을 형성하는가?)

This verification is doable in polynomial time ⇒ NP.
→ 정점 수 n일 때, 확인해야 할 간선 수는 n개
→ 검증 시간은 O(n) 또는 O(n²) 로, 다항 시간 내 가능

---

NP Example 5: Subset Sum

Problem: Given a set of positive integers S and a target M, find if any subset sums to M.
정수 집합 S와 목표 값 M이 주어졌을 때, 어떤 부분집합을 선택해서 그 합이 정확히 M이 되는지를 찾는 문제

Decision version: Is there a subset of S whose sum is exactly M?
S의 부분집합 중 합이 정확히 M이 되는 것이 존재하는가?

→ 예/아니오로 대답 가능

Guessing stage: Pick a subset.
비결정적 알고리즘이라고 가정하고, 어떤 부분집합을 임의로 골라서 추측

Verification stage: Add elements of the subset and check if the sum equals M.

• 선택한 부분집합의 원소들을 모두 더해서, 그 합이 목표값 M과 같은지 확인.

Sum check is linear ⇒ polynomial time ⇒ in NP.

→ n개의 원소에 대해 덧셈만 수행하면 되므로 시간 복잡도는 O(n)

---

NP Example 6: Bin Packing

Problem: Given n objects with sizes 0 < si ≤ 1, what is the minimum number of bins (capacity 1) needed to pack them?

n개의 물건이 있고, 각 물건의 크기는 0<si≤1입니다.
용량이 1인 상자(bin) 들이 있을 때, 모든 물건을 넣기 위해 필요한 최소 상자 수는 몇 개인가?

Decision version: Can all objects be packed into k bins?

“이 물건들을 k개의 상자에 모두 넣을 수 있는가?” → 예/아니오로 대답할 수 있게 바꿈.

Guessing stage: Assign objects to bins.
각 물건이 어떤 상자에 들어가는지를 제시

Verification stage: For each bin, check if the total sum of sizes ≤ 1.
추측한 배정이 유효한지 확인하기 위해, 각 상자의 총 물건 크기를 더해서 1을 초과하지 않는지 확인.

Since this check is polynomial in n, the problem is in NP.

---

NP Example 7: CNF Satisfiability

Problem:

Given a CNF formula (conjunction of clauses, each a disjunction), is there a truth assignment that satisfies the formula?
어떤 참/거짓(True/False) 변수 할당이 이 논리식을 참(True)으로 만들 수 있는가?

Guessing stage: Assign True/False to each variable.
비결정적 알고리즘이라고 가정하고,
모든 변수에 대해 참(True) 또는 거짓(False) 으로 값을 할당.

Verification stage: Plug in the assignment and check if the entire formula evaluates to True.

• 각 절을 순서대로 확인
• 각 절 안의 리터럴 중 하나라도 참이면 그 절은 참
• 모든 절이 참이면 전체 CNF는 참

This checking can be done in polynomial time ⇒ problem is in NP.

변수 개수가 n, 절이 m개이면
→ 시간 복잡도는 O(n × m) 이내
→ 검증은 다항 시간 내 가능