함수 문제

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

1. 개요
2. 정의
- 2.1. 형식적 정의
3. 주요 복잡도 클래스
4. 주요 함수 문제 예시
5. 자기 환원성 (Self-reducibility)
6. 환원 (Reductions)과 완전 문제 (Complete problems)
참조

1. 개요

함수 문제는 주어진 입력에 대해 특정 조건을 만족하는 출력을 찾는 문제로, 입력과 출력 사이의 관계를 정의한다. 알고리즘이 함수 문제를 해결한다는 것은, 모든 입력에 대해 조건에 맞는 출력을 생성하거나, 그러한 출력이 없으면 거부하는 것을 의미한다. 주요 복잡도 클래스에는 솔루션을 다항 시간 내에 검증할 수 있지만 찾을 수 없는 FNP, 솔루션을 다항 시간 내에 찾을 수 있는 FP, 모든 입력에 대해 해가 존재하는 TFNP 등이 있다. 함수 문제의 예시로는 FSAT, 외판원 문제, 최대 클릭 문제, 정수 인수분해 문제 등이 있으며, 자기 환원성, 환원, FNP-완전 문제 등과 같은 개념을 통해 문제의 복잡성을 분석한다.

더 읽어볼만한 페이지

계산 문제 - 다체 문제
다체 문제는 상호작용하는 여러 물체의 운동을 다루는 문제로, 특히 중력적으로 상호작용하는 천체들의 운동을 예측하는 문제가 대표적이며, 삼체 문제부터는 해석적 해를 구하기 어려워 섭동 이론이나 수치 해석 등의 방법이 활용된다.
계산 문제 - 최적화 문제
최적화 문제는 주어진 제약 조건 하에 특정 목적 함수의 값을 최소화하거나 최대화하는 해를 찾는 문제로, 제약 조건 유무, 함수 종류, 변수 성격에 따라 다양한 유형으로 나뉜다.

함수 문제

2. 정의

함수 문제는 입력과 출력 간의 관계로 정의된다. 어떤 알고리즘이 함수 문제를 해결한다는 것은 주어진 입력에 대해 올바른 출력을 생성하거나, 올바른 출력이 없으면 거부한다는 것을 의미한다.

2. 1. 형식적 정의

함수 문제

P

는 알파벳

\Sigma

에 대한 관계

R

을 문자열로 정의한다.

:

R \subseteq \Sigma^* \times \Sigma^*.

어떤 알고리즘이

P

를 해결한다는 것은,

(x, y) \in R

을 만족하는

y

가 존재하는 모든 입력

x

에 대해, 그 알고리즘이 그러한

y

중 하나를 생성하고, 그러한

y

가 없으면 거부한다는 의미이다.

3. 주요 복잡도 클래스

함수 문제는 복잡도에 따라 여러 클래스로 분류된다. 주요 복잡도 클래스는 다음과 같다.

클래스	설명
FP	결정적 튜링 머신에 의해 다항 시간 내에 해결되는 함수 문제의 클래스이다.
FNP	비결정적 튜링 머신에 의해 다항 시간 내에 해결되는 함수 문제의 클래스이다.
TFNP	FNP에 속하는 것 중 반드시 해가 존재하는 문제의 클래스이다.
PLS, PPP, PPA, PPAD	PLS 이하, TFNP에 포함되는 보다 구체적인 문제의 클래스이다.^[1]

3. 1. FP (Function P)

결정적 튜링 머신에 의해 다항 시간 내에 해결되는 함수 문제들의 집합이다.

3. 2. FNP (Function NP)

임의의 결정 문제

L

을 '''NP''' 클래스에 속한다고 가정하자. '''NP'''의 정의에 따라, 'yes'로 답이 나오는 각 문제 인스턴스

x

는 'yes' 답변에 대한 증거 역할을 하는 다항식 크기의 증명서

y

를 갖는다. 따라서 이러한 튜플

(x,y)

의 집합은 관계를 형성하며, 이는 "L에

x

가 주어졌을 때,

x

에 대한 증명서

y

를 찾아라"라는 함수 문제를 나타낸다. 이 함수 문제는

L

의 ''함수 변형''이라고 불리며, FNP에 속한다.

'''FNP'''는 솔루션을 효율적으로 (즉, 입력 길이의 다항 시간 내에) ''검증''할 수 있지만 반드시 효율적으로 ''찾을'' 수 없는 점에서, '''NP'''의 함수 클래스 아날로그로 생각할 수 있다. 반대로 FP 클래스는 '''P'''의 함수 클래스 아날로그로 생각할 수 있으며, 솔루션을 다항 시간 내에 찾을 수 있는 함수 문제로 구성된다.

'''FNP'''는 비결정적 튜링 머신에 의해 다항 시간 내에 해결되는 함수 문제의 클래스이다.

3. 3. TFNP (Total FNP)

'''TFNP'''는 FNP에 속하며, 모든 입력에 대해 반드시 해가 존재하는 함수 문제들의 집합이다. 이 클래스에는 해의 존재가 보장되는 특정 전략적 게임에서 순수한 내시 균형을 계산하는 것과 같은 문제가 포함된다. 또한, 만약 '''TFNP'''가 어떤 '''FNP-완전''' 문제를 포함한다면,

\mathbf{NP} = \textbf{co-NP}

가 성립한다.

3. 4. 기타 클래스

PLS (다항 로컬 탐색), PPP (다항 비둘기집 원리), PPA (다항 패리티 논증), PPAD (방향 그래프를 이용한 다항 패리티 논증)는 모두 TFNP에 포함되는 문제의 클래스이다.^[1]

4. 주요 함수 문제 예시

다음은 함수 문제의 예시이다.

충족 할당 문제: 결정 문제인 충족 가능성 문제와 대비하여 이렇게 쓰인다.
최대 클릭 문제
외판원 문제

4. 1. FSAT (Functional Boolean Satisfiability Problem)

'''FSAT'''(Functional Boolean Satisfiability Problem, 함수적 부울 만족 가능성 문제)는 '''SAT''' 결정 문제의 함수 버전이다. 이 문제는 다음과 같이 정의할 수 있다.

:

x_1, \ldots, x_n

변수를 갖는 부울 공식

\varphi

가 주어졌을 때,

\varphi

가 참(TRUE)으로 평가되도록 하는 할당

x_i \rightarrow \{ \text{TRUE}, \text{FALSE} \}

을 찾거나, 그러한 할당이 존재하지 않음을 결정한다.

SAT 알고리즘은 공식

\varphi

를 입력받아 "만족 불가능" 또는 "만족 가능"을 반환해야 하지만, FSAT 알고리즘은 후자의 경우 만족하는 할당을 반환해야 한다.

4. 2. 외판원 문제 (Traveling Salesman Problem)

외판원 문제는 주어진 모든 도시를 한 번씩 방문하고 시작점으로 돌아오는 최단 경로를 찾는 문제이다. 이 문제는 함수 문제의 한 예시로 언급된다. Traveling Salesman Problem^영어

4. 3. 최대 클릭 문제 (Maximum Clique Problem)

그래프에서 가장 큰 완전 부분 그래프(클릭)를 찾는 문제이다.

4. 4. 정수 인수분해 문제 (Integer Factorization Problem)

정수 인수분해 문제는 주어진 정수를 소인수들의 곱으로 분해하는 문제이다. 이 문제가 자기 환원 가능하지 않을 것이라는 추측이 있다.

5. 자기 환원성 (Self-reducibility)

어떤 '''NP''' 문제의 함수 변형을 원래 문제를 결정하는 오라클을 사용하여 다항 시간 내에 해결할 수 있다면, 그 문제는 *자기 환원 가능*하다고 한다. 모든 '''NP-완전''' 문제는 자기 환원 가능하다.^[1] 정수 인수분해 문제는 자기 환원 가능하지 않을 것으로 추측되는데, 왜냐하면 정수가 소수인지 결정하는 것은 '''P'''에 속하기(쉽기) 때문이며^[1], 반면 정수 인수분해 문제는 고전 컴퓨터에게 어렵다고 여겨지기 때문이다.

자기 환원 가능성에 대한 몇 가지 (약간 다른) 정의가 있다.^[2]^[3]^[4]

6. 환원 (Reductions)과 완전 문제 (Complete problems)

함수 문제는 환원될 수 있는데, 이는 결정 문제와 매우 유사하다. 함수 문제 $\Pi_R$ 과 $\Pi_S$ 가 주어졌을 때, 다항 시간 내에 계산 가능한 함수 $f$ 와 $g$ 가 존재하여 $R$ 의 모든 인스턴스 $x$ 와 $S$ 의 가능한 해 $y$ 에 대해 다음이 성립하면 $\Pi_R$ 이 $\Pi_S$ 로 환원된다고 한다.

만약 $x$ 가 $R$ -해를 가진다면, $f(x)$ 는 $S$ -해를 가진다.
$(f(x), y) \in S \implies (x, g(x,y)) \in R.$

따라서 '''NP-완전''' 문제와 유사한 '''FNP-완전''' 문제를 정의하는 것이 가능하다.

문제

\Pi_R

은 모든 '''FNP'''의 문제가

\Pi_R

로 환원될 수 있다면 '''FNP-완전'''이다. '''FNP-완전''' 문제의 복잡도 클래스는 '''FNP-C''' 또는 '''FNPC'''로 표기한다. 따라서 문제 '''FSAT''' 또한 '''FNP-완전''' 문제이며,

\mathbf{P} = \mathbf{NP}

인 것은

\mathbf{FP} = \mathbf{FNP}

인 것과 동치이다.

참조

_[1] 논문 PRIMES is in P http://www.cse.iitk.[...]
_[2] 논문 On self-reducibility and weak P-selectivity
_[3] 논문 Optimal algorithms for self-reducible problems
_[4] 논문 Natural self-reducible sets

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

문의하기 : help@durumis.com