1-3
개념 사전
글을 읽다 막히는 낱말의 뜻.
- 2-SAT2-SAT괄호마다 항이 두 개인 SAT — 이것은 빨리 풀린다
- 3-SAT3-SAT괄호마다 항이 세 개인 꼴로 제한한 SAT
- AC⁰AC⁰깊이가 상수로 얕고 크기가 다항인 회로로 풀리는 문제의 모임
- ACC⁰ACC⁰AC⁰ 회로에 「m 으로 나눈 나머지 세기」 게이트를 더한 것
- BPPBPP (bounded-error probabilistic polynomial time)동전을 던져 가며 다항 시간에, 높은 확률로 옳게 풀 수 있는 문제의 모임
- BQPBQP (bounded-error quantum polynomial time)양자 컴퓨터가 다항 시간에, 높은 확률로 옳게 풀 수 있는 문제의 모임
- coNPcoNP답이 「아니오」일 때 그 증거를 다항 시간에 검증할 수 있는 문제의 모임
- EXPEXP (EXPTIME, exponential time)지수 시간 안에 풀 수 있는 결정 문제의 모임
- NEXPNEXP (NEXPTIME, nondeterministic exponential time)지수 길이의 증거를 지수 시간에 검증할 수 있는 문제의 모임
- NPNP (nondeterministic polynomial time)답이 「예」일 때 그 증거를 다항 시간에 「검증할 수 있는」 결정 문제의 모임
- NP-난해NP-hardNP 의 어떤 문제보다도 쉽지 않은 문제
- NP-완전NP-completeNP 안에서 가장 어려운 문제들
- NP-중간NP-intermediateNP 에 있지만 P 도 아니고 NP-완전도 아닌 문제
- PP (polynomial time)다항 시간 안에 「풀 수 있는」 결정 문제의 모임
- P/polyP/poly입력 길이마다 따로 만든 작은(다항 크기) 회로로 풀 수 있는 문제의 모임
- PCP 정리PCP theorem (probabilistically checkable proofs)증명의 몇 군데만 무작위로 들춰 봐도 옳고 그름을 가릴 수 있다는 정리
- permanent 와 determinantpermanent vs. determinant식은 거의 같은데 계산의 어려움은 전혀 다른 두 행렬 함수
- PSPACEPSPACE (polynomial space)다항 크기의 기억 공간으로 풀 수 있는 결정 문제의 모임
- 검증자와 증거verifier, certificate (witness)제시된 답이 맞는지 다항 시간에 확인하는 알고리즘과, 그 제시된 답
- 결정 문제decision problem답이 「예」 아니면 「아니오」인 문제
- 결정 불가능undecidable시간을 아무리 줘도 어떤 알고리즘으로도 풀 수 없음
- 그래프 동형graph isomorphism두 그래프가 점의 이름만 다르고 모양은 같은지 묻는 문제
- 그래프 색칠(3색칠)graph coloring (3-coloring)이웃한 점끼리 색이 다르게 칠할 수 있는지 묻는 문제
- 근사 알고리즘approximation algorithm최적은 아니어도 최적에서 일정 비율 안의 답을 보장하는 빠른 알고리즘
- 기하적 복잡도 이론geometric complexity theory (GCT)대수기하와 표현론으로 복잡도 하한을 증명하려는 장기 연구 계획
- 논리 회로(회로 복잡도)Boolean circuit (circuit complexity)AND·OR·NOT 소자를 이어 만든 계산 모형과, 그 크기로 재는 어려움
- 다섯 세계Impagliazzo's five worldsP 대 NP 와 암호의 가능성에 따라 그려 본 다섯 가지 가능한 세상
- 다항 시간polynomial time단계 수가 n, n², n³ 처럼 n^k 꼴로 묶이는 빠르기
- 다항 위계polynomial hierarchy (PH)NP 와 coNP 를 층층이 쌓아 올린 복잡도 종류의 탑
- 단조 회로monotone circuitNOT 없이 AND 와 OR 만 쓰는 회로
- 대각선 논법diagonalization모든 기계와 적어도 한 군데서 다르게 답하는 문제를 만들어 내는 증명법
- 대수화algebrization산술화 기법까지 아우르도록 상대화를 넓힌 개념 — 셋째 장벽
- 대화형 증명(IP)interactive proof system (IP)검증자가 증명자에게 무작위로 질문을 던져 가며 확인하는 증명
- 밀레니엄 문제Millennium Prize ProblemsClay 수학연구소가 문제마다 100만 달러를 건 일곱 개의 수학 난제
- 배낭 문제knapsack problem무게 한도 안에서 가치가 가장 크게 물건을 담는 문제
- 복잡도 종류complexity class푸는 데 드는 자원이 비슷한 문제들의 모임
- 부분합 문제subset sum problem수 몇 개를 골라 합을 정확히 목표값으로 만들 수 있는지 묻는 문제
- 분해 증명(resolution)resolution두 절에서 서로 반대인 항을 지워 새 절을 끌어내는 규칙 하나짜리 증명 체계
- 비결정적 튜링 기계nondeterministic Turing machine갈림길마다 여러 길을 고를 수 있는 가상의 기계
- 산술화arithmetization논리식을 다항식으로 바꿔 대수의 도구로 다루는 기법
- 상대화relativization모든 기계에 같은 오라클을 붙여도 그대로 통하는 증명의 성질 — 첫째 장벽
- 소수 판별primality testing주어진 수가 소수인지 아닌지 가려내는 문제 — 빨리 풀린다
- 시간 복잡도time complexity입력이 커질 때 계산 단계 수가 늘어나는 정도
- 시간 위계 정리time hierarchy theorem시간을 충분히 더 주면 정말로 더 많은 문제를 풀 수 있다는 정리
- 알고리즘algorithm문제를 푸는, 유한하고 모호함 없는 절차
- 오라클(신탁)oracle특정 문제의 답을 한 단계 만에 알려 주는 가상의 블랙박스
- 외판원 문제travelling salesman problem (TSP)모든 도시를 한 번씩 들르고 돌아오는 가장 짧은 길 찾기
- 유사난수 생성기pseudorandom generator (PRG)짧은 난수를 「진짜 난수와 구별할 수 없는」 긴 수열로 늘리는 알고리즘
- 인수분해(소인수분해)integer factorization큰 수를 소수의 곱으로 쪼개는 문제
- 일방향 함수one-way function계산하기는 쉽지만 거꾸로 되돌리기는 어려운 함수
- 입력 크기input size입력을 적는 데 드는 글자(비트) 수
- 자연 증명natural proofs지금까지의 회로 하한 증명이 공통으로 가진 꼴과, 그 꼴의 한계 — 둘째 장벽
- 정점 덮개vertex cover모든 변에 적어도 한쪽 끝이 닿도록 고른 점들의 집합
- 정지 문제halting problem프로그램이 언젠가 멈출지 영원히 돌지 미리 판정하는 문제 — 풀 수 없다
- 증명 복잡도proof complexity참인 명제를 증명하는 데 증명이 얼마나 길어야 하는지 연구하는 분야
- 지수 시간exponential time단계 수가 2ⁿ 처럼 불어나, 입력이 조금만 커져도 감당 못 하는 빠르기
- 최소 회로 크기 문제(MCSP)minimum circuit size problem (MCSP)주어진 함수를 계산하는 가장 작은 회로가 얼마나 작은지 묻는 문제
- 충족 가능성 문제(SAT)Boolean satisfiability problem (SAT)논리식을 참으로 만드는 변수 값이 있는지 묻는 문제
- 콜모고로프 복잡도Kolmogorov complexity어떤 문자열을 찍어 내는 가장 짧은 프로그램의 길이
- 쿡–레빈 정리Cook–Levin theoremSAT 가 NP-완전이라는, NP-완전 이론의 출발점이 된 정리
- 큰-O 표기법big O notation증가율의 위쪽 한계를 간단히 적는 표기
- 클릭clique서로 빠짐없이 이어진 점들의 모임
- 탈무작위화derandomization무작위를 쓰는 알고리즘에서 무작위를 없애는 일
- 튜링 기계Turing machine「계산」이 무엇인지 수학적으로 정한 표준 모형
- 평균적 복잡도average-case complexity가장 고약한 입력이 아니라 「보통의」 입력에서 문제가 얼마나 어려운지
- 하한lower bound「어떤 방법으로도 이보다 적은 자원으로는 못 푼다」는 증명
- 해밀턴 경로Hamiltonian path모든 점을 정확히 한 번씩 지나는 길
- 환산(다항 시간 환산)polynomial-time reduction한 문제를 다른 문제로 바꿔서 푸는 방법
- 휴리스틱heuristic보장은 없지만 실제로는 잘 통하는 요령