計算 複雜度 理論 (計算 複雜度 理論, 英語 : Computational complexity theory )은 컴퓨터 科學 에서 計算 理論 의 分野로, 計算 問題 를 푸는 알고리즘 을 複雜度에 따라 分類하여 問題의 모임 을 構成하는 方法을 硏究한다. 이 때 알고리즘의 修行은 實際 컴퓨터가 할 수 있지만, 評價하는 데에는 튜링 機械 와 關聯이 있는 정량화된 方法을 使用한다.

複雜度의 基準은 알고리즘이 消耗하는 所要 時間과 메모리 使用量 等의 資源이다. 前者를 時間 複雜度 , 後者를 空間 複雜度 라 한다. 一般的으로 이와 같은 時空間 等의 資源은 入力의 크기에 依存하는 것으로 取扱한다.

複雜度 模型 [ 編輯 ]

 이 部分의 本文은 튜링 機械 입니다.

알고리즘의 修行은 一般的으로 튜링 機械 와 그 變種을 基準으로 한다.

大文字 O 表記法 [ 編輯 ]

 이 部分의 本文은 漸近 表記法 입니다.

漸近 表記法 은 複雜度를 表記하는 주된 方法이다.

複雜度 種類 [ 編輯 ]

 이 部分의 本文은 複雜度 種類 입니다.

複雜度 種類 는 時間 複雜度와 空間 複雜度를 包括하는 問題의 集合이다. 어떤 複雜度 種類의 定義는 다음과 關聯이 있다.

• 日程 複雜度를 要求하는 抽象 機械 의 模型. 決定論的 튜링 機械 , 非決定論的 튜링 機械 , 陽子的 튜링 機械 , 모노톤 回로 等.
• 問題의 種類. 決定 , 函數 , 셈 , 最適化 等.

複雜度를 定義하는 주된 方法은 다음과 같다.

主要 複雜度들은 다음과 같이 定義된다. ( p(n) 은 入力 크기 n 에 關한 多項式 이다.)

問題들 [ 編輯 ]

P-NP 問題 [ 編輯 ]

 이 部分의 本文은 P-NP 問題 입니다.

外部 링크 [ 編輯 ]

위키미디어 共用 에 關聯된
미디어 分類가 있습니다.

計算 複雜度 理論

• “Computational complexity classes” . 《Encyclopedia of Mathematics》 (英語). Springer-Verlag. 2001. ISBN   978-1-55608-010-4 .