알려진 부분 결과
문제 자체는 못 풀었지만 확실히 증명된 것들.
- 한눈에 보는 부분 결과 — 확실히 증명된 것들
P 대 NP 문제는 풀리지 않았지만, 문제를 조금 약하게 바꾼 여러 명제는 엄밀히 증명되어 있다. 대표 결과를 표 하나에 모으고, 각각이 P 대 NP 에서 얼마나 떨어져 있는지 짚는다.
- 시간 위계 정리 — 시간을 더 주면 더 풀 수 있다
Hartmanis 와 Stearns 의 시간 위계 정리는 시간을 충분히 더 주면 풀 수 있는 문제가 반드시 늘어난다는 것을 대각선 논법으로 증명한다. P ≠ EXP 가 여기서 나온다. 그러나 같은 방법으로 P 와 NP 사이는 가르지 못한다.
- PARITY ∉ AC⁰ — 얕은 회로는 홀짝도 세지 못한다
층수가 상수이고 크기가 다항식인 회로(AC⁰)는 입력에 든 1 의 개수가 홀수인지 계산하지 못한다. Furst–Saxe–Sipser 와 Ajtai 가 처음 보였고 Håstad 의 전환 보조정리가 거의 최적의 하한을 주었다. Razborov 와 Smolensky 는 이를 나머지 게이트가 달린 회로로 넓혔다.
- 단조 회로 하한 — NOT 없이는 클릭 문제를 풀 수 없다
Razborov 는 1985년에 AND 와 OR 만 쓰는 단조 회로로 클릭 문제를 풀려면 다항식보다 빨리 커지는 크기가 든다는 것을 증명했다. NP-완전 문제를 상대로 다항식을 넘는 하한을 얻은 결과였지만, NOT 게이트 하나가 이 방법과 일반 회로 사이를 가로막는다.
- NEXP ⊄ ACC⁰ — 빠른 알고리즘이 하한을 낳는다
Ryan Williams 는 비결정적 지수 시간(NEXP)에 다항 크기 ACC⁰ 회로로 풀 수 없는 문제가 있음을 증명했다. 회로의 충족 가능성을 전수 조사보다 조금 빨리 푸는 알고리즘에서 하한을 끌어내는 방법이며, Murray–Williams 가 이를 비결정적 준다항 시간으로 끌어내렸다. 이 정리가 말하는 것과 말하지 않는 것을 구별한다.
- IP = PSPACE — 묻고 답하며 확인할 수 있는 것의 범위
무작위로 질문을 던지는 다항 시간 검증자가 전능한 증명자와 대화해 확인할 수 있는 문제는 정확히 다항 공간 문제다. Lund–Fortnow–Karloff–Nisan 과 Shamir 가 산술화 기법으로 증명했으며, 상대화하지 않는 증명의 대표 사례다.
- PCP 정리 — 증명을 몇 군데만 읽고 검사하기
PCP 정리는 NP 문제의 증거를 상수 개의 자리만 읽어도 확률적으로 검사할 수 있는 꼴로 다시 쓸 수 있다고 말한다(NP = PCP(log n, 1)). 이 정리는 「근사해를 구하는 것도 정확히 푸는 것만큼 어렵다」는 결과들과 같은 말이다.
상태 표시의 뜻
- 검토 중
- 관리자가 읽고 있습니다.
- 보완 필요
- 고칠 것이 있습니다. 무엇인지는 상태 설명에 적혀 있습니다.
- 검토 완료
- 내용을 확인했습니다. 증명이 옳다는 뜻이 아닙니다.
- 주목
- 눈여겨볼 만한 자료입니다.
- 결함 확인
- 알려진 결함이 있습니다. 근거는 상태 설명에 적혀 있습니다.
- 보관
- 더 다루지 않는 자료입니다.