계산 복잡도 이론

위키백과 ― 우리 모두의 백과사전.

전산학에서 계산 복잡도 이론(Computational complexity theory)이란 계산 이론의 하나로, 계산 문제의 소요 시간, 메모리 사용량 등을 연구하는 이론이다.

이 글은 전산학에 관한 토막글입니다. 서로의 지식을 모아 알차게 문서를 완성해 갑시다.

v • d • e 주요 복잡도 종류 (더 보기)
P · NP · co-NP · NP-C · co-NP-C · NP-난해 · UP · #P · #P-C · L · NL · NC · P-C · PSPACE · PSPACE-C · EXPTIME · EXPSPACE · PR · RE · co-RE · RE-C · co-RE-C · R · BQP · BPP · RP · ZPP · PCP · IP · PH

v • d • e 컴퓨터 과학의 주요 분야
수학적 기초	수리논리학 · 집합론 · 정수론 · 그래프 이론 · 형 이론 · 범주론 · 수치 해석
계산 이론	오토마타 이론 · 계산 가능성 이론 · 계산 복잡도 이론 · 양자 계산 이론
알고리즘 & 자료 구조	알고리즘 · 자료 구조 · 계산 기하학
프로그래밍 언어 & 컴파일러	구문 분석 · 컴파일러 · 인터프리터 · 프로그래밍 언어 · 구조적 프로그래밍 · 객체 지향 프로그래밍
병행,병렬 & 분산 시스템	병행 컴퓨팅 · 분산 컴퓨팅 · 병렬 컴퓨팅 · 그리드 컴퓨팅 · 클라우드 컴퓨팅 · IaaS · PaaS · SaaS
소프트웨어 공학	요구 분석 · 소프트웨어 설계 · 컴퓨터 프로그래밍 · 형식수법 · 소프트웨어 테스트 · 소프트웨어 개발
시스템 아키텍처	컴퓨터 아키텍처 · 마이크로아키텍처 · 운영 체계
통신 & 네트워크	컴퓨터 오디오 · 라우팅 · 네트워크 토플로지 · 암호학
데이터베이스	데이터 마이닝 · RDBMS · SQL
인공 지능	자동추론 · 전산언어학 · 컴퓨터 비전 · 진화 연산 · 기계 학습 · 자연 언어 처리 · 로봇학
컴퓨터 그래픽	시각화 · 영상 처리
인간과 컴퓨터 상호 작용	Computer accessibility · 사용자 인터페이스 · 착용 컴퓨터 · 유비쿼터스 컴퓨팅 · 가상현실
계산과학	인공생명 · 생물정보학 · 인지과학 · 계산화학 · 계산론적 신경과학 · 계산물리학 · 수치 해석 · Symbolic mathematics
정보보호	암호학 · 물리보안 · 소프트웨어 보안 · 인터넷 보안 · 네트워크 보안 · 해킹 · 크래킹