계산 복잡도
1. 개요
1. 개요
계산 복잡도는 알고리즘이 특정 문제를 해결하는 데 필요한 계산 자원의 양을 연구하는 이론 컴퓨터 과학의 핵심 분야이다. 여기서 자원은 주로 실행에 걸리는 시간(시간 복잡도)과 사용하는 메모리 공간(공간 복잡도)을 의미한다. 이 이론은 문제의 본질적인 어려움을 이해하고, 효율적인 알고리즘의 존재 여부를 판단하며, 서로 다른 문제들 간의 계산적 난이도를 비교하는 틀을 제공한다.
분석의 핵심 도구는 점근 표기법, 특히 빅 오 표기법이다. 이는 입력 크기가 커질 때 알고리즘의 자원 사용량이 어떻게 증가하는지를 추상적으로 표현하여, 상수 계수나 낮은 차수의 항과 같은 세부 사항을 무시하고 성장 추세만을 포착한다. 이를 통해 알고리즘의 효율성을 이론적으로 비교하고 분류할 수 있다.
계산 복잡도 이론의 중요한 성과는 복잡도 클래스라는 개념을 통해 다양한 문제들을 체계적으로 분류한 것이다. 대표적으로, 다항 시간에 해결 가능한 문제들의 클래스인 P와, 해답을 다항 시간 내에 검증할 수 있는 문제들의 클래스인 NP가 있다. P-NP 문제는 이 두 클래스가 실제로 같은지 다른지에 관한 미해결 난제로, 클레이 수학연구소의 밀레니엄 문제 중 하나이다.
이 분야는 알고리즘 분석의 기초를 이루며, 암호학의 안전성 증명, 최적화 문제의 접근법, 그리고 인공지능과 계산 이론의 여러 영역에 깊이 관여한다.
2. 시간 복잡도
2. 시간 복잡도
2.1. 점근적 표기법
2.1. 점근적 표기법
점근적 표기법은 알고리즘의 효율성을 분석할 때 핵심적으로 사용되는 수학적 도구이다. 이 표기법은 입력 크기가 충분히 커질 때 알고리즘이 요구하는 자원(주로 시간 또는 공간)의 증가 양상을 표현한다. 정확한 실행 시간을 계산하는 대신, 입력 크기에 대한 함수로 자원 사용량의 증가 추세를 파악하는 데 중점을 둔다.
가장 널리 사용되는 점근적 표기법은 빅 오 표기법이다. 빅 오 표기법은 알고리즘의 자원 사용량에 대한 상한을 나타낸다. 예를 들어, 어떤 알고리즘의 시간 복잡도가 O(n^2)이라면, 이 알고리즘의 실행 시간은 최악의 경우 입력 크기 n의 제곱에 비례하여 증가함을 의미한다. 이는 해당 알고리즘의 성능이 n^2보다 더 빠르게 증가하지 않는다는 점을 보장한다.
빅 오 외에도 주요 점근적 표기법으로는 오메가 표기법과 세타 표기법이 있다. 오메가 표기법은 알고리즘의 자원 사용량에 대한 하한을 나타낸다. 예를 들어, Ω(n log n)은 알고리즘이 최소한 n log n에 비례하는 시간이 필요함을 의미한다. 세타 표기법은 빅 오와 오메가의 교집합으로, 알고리즘의 자원 사용량이 정확히 특정 함수와 같은 비율로 증가함을 나타낸다. 즉, Θ(f(n))은 상한과 하한이 모두 f(n)임을 의미한다.
이러한 점근적 표기법을 통해 우리는 다양한 알고리즘의 효율성을 이론적으로 비교하고 분류할 수 있다. 예를 들어, 선형 탐색의 시간 복잡도는 O(n)이고, 이진 탐색은 O(log n)이다. 점근적 분석은 상수 계수나 낮은 차수의 항을 무시하기 때문에, 입력이 매우 큰 경우 어떤 알고리즘이 더 우수한지에 대한 명확한 통찰을 제공한다. 이는 계산 복잡도 이론의 기초를 이루며, P와 NP 같은 복잡도 클래스를 정의하는 데 필수적이다.
2.2. 대표적인 시간 복잡도 클래스
2.2. 대표적인 시간 복잡도 클래스
계산 문제의 시간 복잡도는 입력 크기에 대한 알고리즘의 실행 시간 증가율로 분류된다. 가장 일반적인 분류는 점근적 표기법, 특히 빅 오 표기법을 사용하여 표현한다. 이는 알고리즘의 성능을 최악의 경우를 기준으로 상한을 나타내며, 실제 코딩과 알고리즘 설계에서 효율성을 판단하는 핵심 도구이다.
대표적인 시간 복잡도 클래스는 다음과 같이 구분할 수 있다. 상수 시간과 로그 시간 복잡도를 갖는 알고리즘은 매우 효율적이라고 평가받는다.
복잡도 | 표기 | 설명 | 예시 알고리즘 |
|---|---|---|---|
상수 시간 | O(1) | 입력 크기와 무관하게 실행 시간이 일정함. | 배열의 인덱스로 원소 접근, 해시 테이블 조회[1] |
로그 시간 | O(log n) | 실행 시간이 입력 크기의 로그에 비례하여 증가함. | 이진 탐색, 균형 이진 탐색 트리 연산 |
선형 시간 | O(n) | 실행 시간이 입력 크기에 정비례하여 증가함. | 배열 순회, 연결 리스트 탐색 |
선형로그 시간 | O(n log n) | 실행 시간이 n log n에 비례하여 증가함. 대부분의 효율적인 정렬 알고리즘이 이에 해당. | 병합 정렬, 힙 정렬, 고속 푸리에 변환 |
이차 시간 | O(n²) | 실행 시간이 입력 크기의 제곱에 비례하여 증가함. | 버블 정렬, 선택 정렬, 두 개의 중첩 루프를 사용하는 단순 알고리즘 |
지수 시간 | O(2ⁿ) | 실행 시간이 입력 크기에 대해 지수적으로 증가함. 큰 입력에 대해 실용적이지 않음. | 모든 부분집합을 나열하는 브루트 포스 알고리즘, 일부 NP-완전 문제의 단순 해법 |
다항식 시간 복잡도(O(nᵏ), k는 상수)는 현실적으로 다루기 쉬운 문제를 정의하는 기준이 된다. 다항식 시간 복잡도 클래스인 P는 이러한 문제들의 집합이다. 반면, 지수 시간 복잡도는 입력이 조금만 커져도 실행 시간이 폭발적으로 증가하여, 알고리즘 분석에서 비효율적인 알고리즘의 대표적 사례이다.
이러한 복잡도 클래스의 이해는 문제의 본질적 어려움, 즉 계산 이론에서 다루는 복잡도 클래스 간의 관계(예: P 대 NP 문제)를 탐구하는 기초가 된다. 또한 암호학이나 최적화 분야에서 실용적인 알고리즘을 선택하거나 문제의 난이도를 추정하는 데 직접적으로 활용된다.
[2] 최악의 경우 충돌이 많을 때는 성능이 저하될 수 있음.
3. 공간 복잡도
3. 공간 복잡도
공간 복잡도는 알고리즘이 실행되는 동안 사용하는 메모리 공간의 양을 입력 크기에 대한 함수로 나타낸다. 시간 복잡도가 실행 시간을 분석한다면, 공간 복잡도는 메모리 사용량을 분석한다. 이는 알고리즘의 효율성을 평가하는 또 다른 핵심 척도이며, 특히 메모리가 제한된 환경에서 중요하게 고려된다.
공간 복잡도 역시 점근 표기법을 사용하여 표현하며, 입력 자체를 저장하는 데 필요한 공간은 일반적으로 포함한다. 예를 들어, 크기 n의 배열을 저장하는 데는 Θ(n)의 공간이 필요하다. 알고리즘이 사용하는 추가적인 작업 공간(예: 재귀 호출 스택, 임시 변수)이 공간 복잡도의 주요 분석 대상이 된다.
시간과 공간 자원 사이에는 종종 트레이드오프 관계가 존재한다. 더 빠른 실행 속도를 얻기 위해 더 많은 메모리를 사용하거나, 메모리를 절약하기 위해 실행 시간이 더 걸리는 알고리즘을 선택할 수 있다. 계산 복잡도 이론에서는 이러한 자원 사용을 체계적으로 분류하기 위해 다양한 복잡도 클래스를 정의하는데, PSPACE는 결정론적 튜링 기계가 다항식 크기의 공간으로 풀 수 있는 문제들의 클래스를 의미한다.
공간 복잡도 분석은 데이터 구조 설계, 컴파일러 최적화, 그리고 인공지능이나 빅데이터 처리와 같이 대용량 데이터를 다루는 분야에서 실용적인 중요성을 가진다. 알고리즘을 선택할 때는 문제의 제약 조건과 사용 가능한 자원에 따라 시간과 공간 효율성을 종합적으로 고려해야 한다.
4. 복잡도 클래스
4. 복잡도 클래스
4.1. P와 NP
4.1. P와 NP
P와 NP는 계산 복잡도 이론에서 가장 핵심적이면서도 유명한 복잡도 클래스이다. 이 두 클래스의 관계를 묻는 P-NP 문제는 컴퓨터 과학의 대표적인 미해결 문제로 꼽힌다.
P 클래스는 결정론적 튜링 기계를 사용하여 다항 시간 내에 해결할 수 있는 모든 결정 문제의 집합을 의미한다. 즉, 문제의 크기에 대한 다항식 함수로 실행 시간이 표현되는 효율적인 알고리즘이 존재하는 문제들이 여기에 속한다. 반면 NP 클래스는 비결정론적 튜링 기계를 사용하면 다항 시간 내에 해결할 수 있는 결정 문제들의 집합으로 정의된다. 더 직관적으로 설명하면, 어떤 문제의 답안이 주어졌을 때 그 답안이 맞는지 틀린지를 다항 시간 내에 확인(verify)할 수 있다면 그 문제는 NP에 속한다고 말한다.
P와 NP의 관계는 간단히 'P가 NP의 부분집합인가'라는 질문으로 요약된다. 모든 P 문제는 당연히 NP 문제이기도 하다. 그러나 그 역, 즉 모든 NP 문제가 P 문제인지, 다시 말해 검증이 쉬운 모든 문제가 실제로 해결하는 것도 쉬운지에 대해서는 아직 알려지지 않았다. 대부분의 학자들은 P와 NP가 다를 것이라고 믿지만, 이를 엄밀하게 증명하거나 반증하는 것은 아직 이루어지지 않았다.
이 문제의 중요성은 실용적 측면에서도 매우 크다. 만약 P와 NP가 같다면, 현재 풀기 어려운 것으로 알려진 수많은 최적화 문제와 암호학적 문제에 효율적인 해법이 존재할 수 있음을 의미한다. 이는 현대 암호 체계의 근간을 흔들 수 있는 결과를 초래할 수 있다.
4.2. NP-완전
4.2. NP-완전
NP-완전은 NP에 속하는 모든 문제를 다항식 시간 내에 환원할 수 있는 문제들의 집합을 가리킨다. 다시 말해, NP-완전 문제 중 하나라도 다항식 시간에 해결할 수 있는 알고리즘이 발견된다면, NP에 속하는 모든 문제를 다항식 시간에 해결할 수 있게 되어 P-NP 문제가 P=NP로 해결된다. 이는 계산 복잡도 이론에서 가장 중요한 개념 중 하나이다.
NP-완전 문제의 대표적인 예로는 외판원 문제, 충족 가능성 문제(SAT), 정점 커버 문제, 해밀턴 경로 문제 등이 있다. 이들은 모두 서로 다항식 시간 환원이 가능하며, 실세계의 다양한 최적화 문제와 스케줄링 문제가 NP-완전임이 증명되어 있다. 이는 이론적으로는 물론 실제 알고리즘 설계와 컴퓨터 과학 전반에 깊은 영향을 미친다.
NP-완전성의 개념은 1971년 스티븐 쿡이 그의 논문 "The Complexity of Theorem Proving Procedures"에서 SAT 문제가 NP-완전임을 증명하면서 정립되었다. 이후 리처드 카프는 21개의 다른 조합 최적화 문제들도 NP-완전임을 보여주어, 이 개념의 중요성과 보편성을 확립했다.
NP-완전 문제들은 다항식 시간 알고리즘이 알려져 있지 않지만, 그렇다고 해서 전혀 풀 수 없는 것은 아니다. 근사 알고리즘, 휴리스틱, 메타휴리스틱 기법 등을 통해 실용적인 시간 내에 만족스러운 해를 찾는 연구가 활발히 진행되고 있다. 또한 양자 컴퓨팅과 같은 새로운 계산 모델이 이러한 문제들의 본질적 난이도를 변화시킬 수 있을지에 대한 탐구도 계속되고 있다.
4.3. NP-난해
4.3. NP-난해
NP-난해는 NP-완전 문제만큼이나 어렵거나 그 이상으로 어려운 문제들의 집합이다. 정확히 말하면, 모든 NP 문제가 다항식 시간 내에 어떤 문제 A로 환원될 수 있다면, 그 문제 A는 NP-난해 문제이다. NP-완전 문제는 NP-난해 문제이면서 동시에 NP에 속하는 문제들의 특별한 부분집합이다. 반면 NP-난해 문제는 NP에 속하지 않을 수도 있다.
따라서 NP-난해 문제는 NP-완전 문제보다 더 넓은 범주를 가진다. NP-난해에는 정지 문제와 같이 결정 불가능한 문제들도 포함될 수 있다. 이는 계산 이론에서 다루는, 어떤 알고리즘으로도 해결할 수 없는 문제를 의미한다. 이러한 문제들은 NP 클래스에 속하지 않으면서도, 모든 NP 문제를 그 문제로 변환할 수 있기 때문에 NP-난해로 분류된다.
NP-난해 문제의 대표적인 예로는 최적화 문제의 결정 문제 버전이 있다. 예를 들어, '주어진 그래프에서 최소 크기의 정점 덮개를 찾아라'라는 최적화 문제는 NP-난해에 속한다. 이 문제의 결정 문제 버전인 '크기 k 이하의 정점 덮개가 존재하는가?'는 NP-완전 문제이다. 이처럼 NP-난해는 이론적으로 매우 어려운 문제들을 포괄하는 개념으로, 실제 알고리즘 분석과 계산 이론에서 중요한 위치를 차지한다.
5. 계산 모델
5. 계산 모델
5.1. 튜링 기계
5.1. 튜링 기계
튜링 기계는 앨런 튜링이 1936년 제안한 추상적인 계산 모델로, 현대 컴퓨터 과학과 계산 이론의 기초를 이루는 개념이다. 이 모델은 모든 알고리즘이 수행할 수 있는 계산을 정확히 정의하고, 계산 가능성의 한계를 탐구하는 데 사용된다. 튜링 기계는 무한히 긴 테이프, 테이프를 읽고 쓸 수 있는 헤드, 그리고 유한한 상태 제어부로 구성된다. 이 단순한 구조에도 불구하고, 튜링 기계는 현대의 모든 디지털 컴퓨터가 수행할 수 있는 계산을 모방할 수 있다는 점에서 강력한 이론적 도구로 인정받는다.
계산 복잡도 이론에서 튜링 기계는 문제를 해결하는 데 필요한 자원의 양을 분석하는 표준 모델로 활용된다. 특히, 시간 복잡도와 공간 복잡도를 정의하고 측정하는 기준이 된다. 예를 들어, 어떤 문제를 결정론적 튜링 기계로 다항식 시간 내에 해결할 수 있다면, 그 문제는 복잡도 클래스 P에 속한다고 말한다. 반면, 비결정론적 튜링 기계를 가정하여 다항식 시간 내에 해결 가능성을 논의함으로써 NP와 같은 보다 넓은 복잡도 클래스를 정의할 수 있다.
이러한 추상화는 실제 컴퓨터의 구체적인 세부 사항(예: 프로세서 속도, 메모리 아키텍처)에 의존하지 않고 계산 문제의 본질적인 난이도를 논할 수 있게 해준다. 튜링 기계 모델을 통해 정지 문제의 불가능성을 증명하거나, P-NP 문제와 같은 근본적인 질문을 제기하는 것이 가능해졌다. 따라서 튜링 기계는 계산 복잡도 이론의 핵심적인 분석 도구이자 이론적 토대라고 할 수 있다.
5.2. 결정론적 vs 비결정론적
5.2. 결정론적 vs 비결정론적
계산 복잡도 이론에서 결정론적과 비결정론적은 계산 모델의 핵심적인 특성을 구분하는 개념이다. 이 구분은 특히 시간 복잡도 클래스를 정의하는 데 근본적인 역할을 한다.
결정론적 튜링 기계는 주어진 입력에 대해 프로그램의 다음 단계가 유일하게 결정되는 모델이다. 즉, 특정 시점의 기계 상태와 테이프의 기호가 주어지면, 다음에 수행할 동작(상태 변화, 기호 쓰기, 헤드 이동)이 하나로 정해져 있다. 현실의 모든 컴퓨터는 이 결정론적 모델을 따르며, 알고리즘의 실행 시간을 분석할 때 일반적으로 이 모델을 가정한다. 반면, 비결정론적 튜링 기계는 각 단계에서 여러 가지 가능한 동작 중 하나를 '추측'하여 선택할 수 있는 이론적 모델이다. 이 모델은 문제를 해결하는 데 필요한 '검증' 시간의 상한을 분석하는 데 유용하게 쓰인다.
이 두 모델의 가장 중요한 차이는 복잡도 클래스 P와 NP의 정의에 반영되어 있다. 클래스 P는 결정론적 튜링 기계로 다항식 시간 내에 해를 *찾을 수 있는* 문제들의 집합이다. 클래스 NP는 비결정론적 튜링 기계로 다항식 시간 내에 해를 *찾을 수 있는*, 또는 동등하게 결정론적 튜링 기계로 다항식 시간 내에 주어진 해가 맞는지 *검증할 수 있는* 문제들의 집합으로 정의된다. NP-완전 문제는 NP 클래스에서 가장 어려운 문제들로, 이들이 결정론적 다항식 시간(P)에 풀릴 수 있는지 여부는 P-NP 문제라는 미해결 난제로 남아 있다.
특성 | 결정론적 튜링 기계 | 비결정론적 튜링 기계 |
|---|---|---|
동작 방식 | 각 단계의 다음 동작이 유일하게 결정됨 | 각 단계에서 여러 가능한 동작 중 선택(추측) 가능 |
현실 구현 | 모든 실제 컴퓨터의 기반 모델 | 물리적으로 구현 불가능한 이론적 모델 |
주요 관련 복잡도 클래스 | ||
해 찾기 vs 검증 | 해를 찾는 과정을 모델링 | 해를 검증하는 능력의 상한을 모델링 |
이러한 계산 모델에 대한 이해는 알고리즘 분석의 기초를 이루며, 계산 이론과 암호학 등 여러 분야에서 문제의 본질적 난이도를 규명하는 데 필수적이다.
6. 하한과 상한
6. 하한과 상한
계산 복잡도 이론에서 하한과 상한은 특정 계산 문제를 해결하는 데 필요한 자원의 양에 대한 이론적 한계를 나타낸다. 상한은 문제를 해결하는 알고리즘이 최악의 경우에 사용하는 자원의 양을 의미하며, 주로 빅 오 표기법을 사용하여 표현한다. 예를 들어, 비교 기반 정렬 알고리즘의 시간 복잡도 상한은 O(n log n)으로 알려져 있다. 이는 해당 문제를 해결하는 알고리즘이 이보다 더 나은 성능을 보장할 수 없음을 의미하는 것이 아니라, 적어도 이 정도의 성능을 갖는 알고리즘이 존재함을 보여준다.
반면 하한은 문제를 해결하는 모든 가능한 알고리즘이 최소한 필요로 하는 자원의 양을 의미하며, 오메가 표기법을 사용하여 표현한다. 동일한 비교 기반 정렬 문제의 시간 복잡도 하한은 Ω(n log n)으로 증명되어 있다. 이는 아무리 뛰어난 알고리즘을 고안하더라도, 비교 연산만을 사용하는 모든 알고리즘은 최악의 경우 적어도 n log n에 비례하는 시간이 필수적으로 소요됨을 의미한다. 상한과 하한이 일치할 때, 즉 Θ(n log n)과 같이 표현될 때, 해당 문제의 정확한 복잡도가 결정된다고 볼 수 있다.
하한을 증명하는 것은 상한을 찾는 것보다 일반적으로 더 어려운 과제이다. 상한은 하나의 구체적인 알고리즘을 제시함으로써 증명할 수 있지만, 하한을 증명하려면 문제를 해결하는 '모든 가능한' 알고리즘에 대해 그 한계가 성립함을 보여야 하기 때문이다. 이러한 하한 증명은 계산 문제의 본질적인 난이도를 규명하는 데 핵심적이며, 계산 이론의 중요한 연구 주제가 된다. 예를 들어, 특정 문제에 대해 다항식 시간 하한이 증명된다면, 그 문제는 P 클래스에 속할 수 없음을 의미하게 된다.
하한과 상한의 분석은 알고리즘 분석의 근간을 이루며, 알고리즘 설계자에게 성능 개선의 여지가 있는지, 또는 이미 최적의 알고리즘에 도달했는지를 판단하는 기준을 제공한다. 또한 복잡도 클래스 간의 관계를 이해하고, P-NP 문제와 같은 근본적인 질문을 탐구하는 데 필수적인 도구로 활용된다.
7. 난이도 증명
7. 난이도 증명
난이도 증명은 특정 계산 문제가 특정 복잡도 클래스에 속함을 엄밀하게 증명하는 과정이다. 이는 주로 문제의 계산적 난이도를 규명하고, 서로 다른 문제들 간의 계산적 관계를 밝히는 데 목적이 있다. 가장 중요한 난이도 증명의 형태는 어떤 문제가 NP-완전임을 보이는 것이다. 이를 위해서는 해당 문제가 NP에 속함과 동시에, 이미 NP-완전으로 알려진 다른 문제를 다항식 시간 내에 그 문제로 변환할 수 있음을, 즉 다항식 시간 변환을 통해 증명한다.
NP-완전성을 증명하는 데 널리 사용되는 기법은 환원이다. 예를 들어, 최초로 NP-완전임이 증명된 충족 가능성 문제는 다른 문제들의 NP-완전성을 증명하는 데 기준점 역할을 한다. 문제 A가 NP-완전임을 증명하려면, 먼저 A가 NP에 속함을 보이고, 이미 알려진 NP-완전 문제 B를 A로 다항식 시간 내에 변환할 수 있음을 보인다. 이는 문제 A가 문제 B 이상으로 어렵다는 것을 의미하며, 따라서 A도 NP-완전이 된다.
난이도 증명은 상한과 하한을 모두 다룬다. 어떤 문제가 특정 복잡도 클래스에 속한다는 것은 그 문제를 해결하는 알고리즘이 존재함을 의미하는 상한 증명이다. 반대로, 어떤 문제가 특정 자원의 양보다 적게 사용해서는 해결될 수 없다는 하한 증명은 훨씬 더 어려운 경우가 많다. 예를 들어, 정렬 문제의 비교 기반 하한이 오메가(n log n)임이 알려져 있다.
이러한 증명들은 계산 이론의 근간을 이루며, 알고리즘 설계의 한계를 이해하고, 암호학의 기반이 되는 난해한 문제를 찾는 데 핵심적인 역할을 한다. 난이도 증명을 통해 P 대 NP 문제와 같은 근본적인 질문에 접근할 수 있다.
8. 계산 복잡도 이론의 주요 문제
8. 계산 복잡도 이론의 주요 문제
계산 복잡도 이론은 여러 중요한 미해결 문제를 안고 있으며, 이 문제들의 해결은 이론 컴퓨터 과학의 핵심 과제로 여겨진다. 가장 유명한 문제는 P-NP 문제이다. 이 문제는 다항 시간에 해결 가능한 문제들의 클래스인 P와 비결정론적 튜링 기계를 사용해 다항 시간에 검증 가능한 해를 가진 문제들의 클래스인 NP가 동일한지 묻는다. 만약 P와 NP가 같다면, 현재 어렵다고 알려진 많은 문제들이 사실은 효율적으로 해결 가능함을 의미하게 된다. 그러나 대부분의 학자들은 P와 NP가 다를 것이라고 추측하고 있다.
P-NP 문제와 밀접하게 연관된 문제로는 NP-완전 문제들의 실제 난이도에 대한 질문이 있다. 만약 P ≠ NP라면, NP-완전 문제들은 다항 시간 내에 해결할 수 없는 본질적으로 어려운 문제가 된다. 반대로, 단 하나의 NP-완전 문제라도 다항 시간 알고리즘이 발견된다면, 모든 NP 문제가 P에 속하게 되어 P = NP가 증명된다. 대표적인 NP-완전 문제로는 외판원 문제, 충족 가능성 문제(SAT), 정점 커버 문제 등이 있다.
계산 복잡도 이론에는 다른 주요 복잡도 클래스들 간의 관계에 대한 근본적인 질문도 존재한다. 예를 들어, PSPACE와 NP의 관계, NP와 공동 NP(co-NP)의 관계, 그리고 확률적 알고리즘을 사용하는 BPP 클래스가 P와 같은지 여부 등이 있다. 또한, 지수 시간이 필요한 문제들의 클래스인 EXPTIME과 PSPACE의 관계도 중요한 연구 주제이다. 이러한 클래스들 간의 포함 관계를 규명하는 것은 계산 가능성의 한계를 이해하는 데 필수적이다.
마지막으로, 문제의 점근적 복잡도에 대한 정확한 하한을 찾는 것도 주요 도전 과제이다. 예를 들어, 정렬 알고리즘 비교 기반 정렬의 하한이 Ω(n log n)임이 알려져 있지만, 많은 다른 문제들에 대해서는 최적 알고리즘이 무엇인지, 또는 그 문제의 본질적인 복잡도 하한이 무엇인지 알려지지 않았다. 이러한 난이도 증명은 알고리즘 설계의 목표를 설정하고, 주어진 문제가 더 이상 개선될 수 없는지 판단하는 기준을 제공한다.
