목차
55 처지: AI-완전, Co-NP, Co-NP-완전, Co-RE-완전, Computers and Intractability: A Guide to the Theory of NP-Completeness, 독립집합, 레오니드 레빈, 배낭 문제, 결정 트리 학습법, 결정론적 알고리즘, 복잡도 종류, 복잡도 종류 목록, 변 색칠, 분할 문제, 부분집합 합 문제, 그래프 분할, 그래프 이론, 그래프 색칠, 근사 알고리즘, 기사의 여행, 노노그램, 스티븐 쿡, 튜링상, 클릭 (그래프 이론), 이징 모형, 조합최적화, 종이접기의 수학, 집합 덮개 문제, 지뢰 찾기, 창고지기, 충족 가능성 문제, 컴퓨터 과학자 목록, 컴퓨터 과학의 미해결 문제 목록, 콰인-매클러스키 알고리즘, 쿡-레빈 정리, 유계오차 확률적 다항시간, 샤프-P, 최단 경로 문제, 양자 컴퓨터, 프리셀, 토론토 대학교, 해밀턴 경로, 알고리즘 분석, 외판원 문제, 완벽 그래프, MAX-SNP, NC (복잡도), NP (복잡도), NP-난해, NPC, ... 색인을 확장하십시오 (5 더) »
AI-완전
AI-완전 (영: AI-complete)은 인공지능의 테마 중에서도 가장 곤란한 것을 가리키는 학술적이지 않은 용어이.
보다 NP-완전와 AI-완전
Co-NP
산 복잡도 이론에서 co-NP는 복잡도 종류이.
보다 NP-완전와 Co-NP
Co-NP-완전
산 복잡도 이론에서 복잡도 종류 co-NP-완전(co-NP-complete)이란 co-NP에서 가장 어려운 문제의 집합을 말. 여기서 어렵다는 것은, P에 들어갈 가능성이 낮다는 뜻이.
Co-RE-완전
co-RE-완전은 복잡도 co-RE에서 완전한 결정 문제의 집합이.
Computers and Intractability: A Guide to the Theory of NP-Completeness
《Computers and Intractability: A Guide to the Theory of NP-Completeness》는 NP-완전 문제를 처음 다룬 전산학의 고전이.
보다 NP-완전와 Computers and Intractability: A Guide to the Theory of NP-Completeness
독립집합
꼭짓점 9개가 극대 독립집합을 나타낸다. 이 그래프의 꼭짓점은 모두 24개이다. 그래프 이론에서, 독립 집합(獨立集合)은 서로 인접하지 않는 꼭짓점들의 집합이.
보다 NP-완전와 독립집합
레오니드 레빈
오니드 레빈 레오니드 아나톨리에비치 레빈(1948년 11월 2일 ~)은 소비에트 연방 드네프로페트로프스크(현 우크라이나의 드니프로페트로우스크)에서 출생한 전산학자, 수학자이.
배낭 문제
250px 배낭 문제(냅색 프라블럼)는 조합 최적화의 유명한 문제이.
보다 NP-완전와 배낭 문제
결정 트리 학습법
정 트리 학습법(decision tree learning)은 어떤 항목에 대한 관측값과 목표값을 연결시켜주는 예측 모델로써 결정 트리를 사용.
결정론적 알고리즘
정론적 알고리즘(deterministic algorithm)은 예측한 그대로 동작하는 알고리즘이.
복잡도 종류
복잡도 종류(複雜度 種類)는 계산 복잡도 이론에서 계산 복잡도에 따라서 문제를 분류한 것이.
복잡도 종류 목록
이 문서는 계산 복잡도 이론에서 다루는 복잡도 종류 목록이.
변 색칠
의 3색 변 색칠 완전 그래프 K_8의 7색 변 색칠 그래프 이론에서, 변 색칠(邊色漆, 은 그래프의 변들에, 같은 색이 인접하지 않도록 색을 부여하는 방법이다. 이를 사용하여 그래프의 불변량을 정의할 수 있다.
보다 NP-완전와 변 색칠
분할 문제
분할 문제(partition problem)는 전산학에서 다루는 NP-완전 문제이.
보다 NP-완전와 분할 문제
부분집합 합 문제
부분집합 합 문제(subset sum problem)는 계산 복잡도 이론과 암호학에 관련된 문제로, 유한 개의 정수로 이루어진 집합이 있을 때 이 집합의 부분집합 중에서 그 집합의 원소를 다 더한 값이 0이 되는 경우가 있는지를 알아내는 문제이.
그래프 분할
분할(graph partitioning) 문제는 그래프를 여러 부분으로 나눌 때, 가능한 한 적게 연결되도록 나누는 문제이.
그래프 이론
6개의 꼭짓점과 7개의 변을 갖는 그래프 그래프 이론(graph理論)은 수학에서 객체 간에 짝을 이루는 관계를 모델링하기 위해 사용되는 수학 구조인 그래프에 대한 연구이.
그래프 색칠
의 3개의 색으로의 색칠. 이 그래프는 2개의 색으로 색칠할 수 없으며, 따라서 이 그래프의 색칠수는 3이다. 그래프 이론에서, 그래프 색칠(graph色漆)은 그래프의 꼭지점들에, 같은 색이 인접하지 않도록 색을 부여하는 방법이.
근사 알고리즘
사 알고리즘(approximation algorithm)은 어떤 최적화 문제에 대한 근사해를 구하는 알고리즘을 의미.
기사의 여행
스판 위에서의 경로의 예 기사의 여행은 체스보드의 나이트에 대한 수학적인 알고리즘 문제의 일종이.
노노그램
예시 노노그램()은 일본의 퍼즐 게임이.
보다 NP-완전와 노노그램
스티븐 쿡
스티븐 아서 쿡(Stephen Arthur Cook, 1939년 12월 14일~)은 미국의 전산학자이다. 1971년 ACM 《SIGACT Symposium on the Theory of Computing》에 실린 논문 〈The Complexity of Theorem Proving Procedures〉에서 NP-완전의 개념을 확립한 것으로 유명하다. 이 논문에 들어있는 쿡의 정리는 충족 가능성 문제가 NP-완전임을 증명하는 것이다.
보다 NP-완전와 스티븐 쿡
튜링상
링 상(튜링 어워드)은 ACM에서 컴퓨터 과학 분야에 업적을 남긴 사람에게 매년 시상하는 상이.
보다 NP-완전와 튜링상
클릭 (그래프 이론)
완전 그래프 K5. 이러한 부분 그래프가 있으면, 그 부분 그래프에 속하는 꼭짓점들은 크기 5인 클릭을 이룬다. 그래프 이론에서, 클릭()은 모든 가능한 변이 존재하는 꼭짓점들의 부분집합이.
이징 모형
통계역학에서, 이징 모형(Ising model)은 강자성체 또는 반강자성체의 간단한 모형이.
보다 NP-완전와 이징 모형
조합최적화
응용수학과 전산학에서 조합최적화는 최적화 문제의 일종으로서, 운용 과학, 알고리즘 이론, 계산 복잡도 이론과 관련되어 있고, 인공지능, 수학, 소프트웨어 공학과 영역이 겹. 조합최적화에서는 일반적으로 어렵다고 보는 문제를.
보다 NP-완전와 조합최적화
종이접기의 수학
종이접기에는 상당한 수학적 함의가 있. 이를 종이접기의 수학이.
집합 덮개 문제
집합 덮개 문제(set cover)는 전산학과 복잡도 이론에서 다루는 오랜 문제로, 어떠한 전체집합과 그 집합의 부분집합들이 주어졌을 때, 부분집합들 중에서 가능한 한 적은 집합을 골라서 그 집합들의 합집합이 원래 전체집합이 되도록, 즉 그 집합들이 원래 전제집합을 '덮도록' 집합을 선택하는 문제이.
지뢰 찾기
KDE에 포함된 지뢰 찾기인 KMines. 지뢰 찾기(Minesweeper)는 혼자서 하는 컴퓨터 게임이.
보다 NP-완전와 지뢰 찾기
창고지기
창조지기 퍼즐을 풀고 있다. 창고지기는 싱킹 래빗(シンキングラビット)에서 제작하여 1982년 12월에 발매한 컴퓨터용 퍼즐 게임이.
보다 NP-완전와 창고지기
충족 가능성 문제
충족 가능성 문제(充足可能性問題, satisfiability problem, SAT)는 어떠한 변수들로 이루어진 논리식이 주어졌을 때, 그 논리식이 참이 되는 변수값이 존재하는지를 찾는 문제이.
컴퓨터 과학자 목록
이 문서는 컴퓨터 과학자의 목록으로서, 컴퓨터 과학 분야에서 활동한 연구가와 저술가의 목록이.
컴퓨터 과학의 미해결 문제 목록
음은 컴퓨터 과학의 주요 미해결 문제를 정리한 것이.
콰인-매클러스키 알고리즘
인-매클러스키 알고리즘(Quine-McCluskey algorithm)은 논리식을 최소화하는 알고리즘이.
쿡-레빈 정리
쿡-레빈 정리(Cook-Levin theorem)는 충족 가능성 문제(SAT)가 NP-완전이라는 것을 증명하는 정리로, 모든 NP 복잡도에 속하는 결정 문제는 다항 시간 내에 충족 가능성 문제로 환산할 수 있다는 것을 의미.
유계오차 확률적 다항시간
유계오차 확률적 다항시간(有界誤差 確率的 多項時間), BPP(Bounded-error, Probabilistic, Polynomial time)는 계산 복잡도 이론에서 확률적 튜링 기계로 모든 문제에 대해서 최대 1/3의 오류가 발생하면서 다항시간에 풀 수 있는 판정 문제의 집합이.
샤프-P
산 복잡도 이론에서 복잡도 종류 #P는 개수를 세는 문제들로 이루어진 집합으로, 여기에 들어 있는 문제는 NP에 속한 판정 문제와 연. 다른 복잡도 종류하고 다르게 #P는 판정문제가 아니라 함수 문제의 집합이.
보다 NP-완전와 샤프-P
최단 경로 문제
이론에서 최단 경로 문제란 가장 짧은 경로에서 두 꼭짓점을 찾는 문제로서, 가중 그래프에서는 구성하는 변들의 가중치 합이 최소가 되도록 하는 경로를 찾는 문제이.
양자 컴퓨터
양자 컴퓨터의 기초가 되는 큐비트를 그림으로 나타내기 위한 블로흐 구 모형 양자 컴퓨팅(量子 -, quantum computing) 또는 양자 컴퓨터(quantum computer)는 얽힘(entanglement)이나 중첩(superposition) 같은 양자역학적인 현상을 이용하여 자료를 처리하는 계산 기계이.
프리셀
리셀은 솔리테어의 일종이.
보다 NP-완전와 프리셀
토론토 대학교
학교(University of Toronto, U of T)는 캐나다 온타리오 주 토론토에 있는 연구 중심 공립 대학이.
해밀턴 경로
정십이면체의 모든 꼭짓점을 지나는 해밀턴 순환 그래프 이론에서, 해밀턴 경로(Hamilton經路)는 모든 꼭짓점을 한 번씩 지나는 경로이.
알고리즘 분석
알고리즘 분석()은 컴퓨터 과학에서 알고리즘을 실행하는데 필요한 (시간과 기억 용량과 같은) 자원의 수를 결정하는 일을 가리.
외판원 문제
외판원 문제의 해결책. 외판원 문제(外販員問題) 또는 순회 외판원 문제는 조합 최적화 문제의 일종이.
완벽 그래프
릭의 크기가 같다. 다른 꼭짓점을 지웠을 때에도 마찬가지 결과가 얻어진다. 그래프 이론에서, 완벽 그래프()는 그 색칠수가 클릭과 특별한 관계를 만족시키는 그래프이.
MAX-SNP
산 복잡도 이론에서 MAX-SNP는 최적화 문제의 근사 가능성에 대한 복잡도 종류이.
NC (복잡도)
산 복잡도 이론에서 NC(Nick's Class)는 프로세서가 다항 개인 병렬 컴퓨터가 다항로그 시간에 판정할 수 있는 판정 문제의 집합이.
NP (복잡도)
NP는 비결정론적 튜링 기계(NTM)로 다항 시간 안에 풀 수 있는 판정 문제의 집합으로, NP는 비결정론적 다항시간(非決定論的 多項時間, Non-deterministic Polynomial time)의 약자이.
NP-난해
NP-난해, NP-hard는 NP에 속하는 모든 판정 문제를 다항 시간에 다대일 환산할 수 있는 문제들의 집합이.
보다 NP-완전와 NP-난해
NPC
NPC는 다음을 뜻.
보다 NP-완전와 NPC
P-완전
산 복잡도 이론에서 복잡도 종류 P-완전은 판정 문제의 집합으로, 병렬 컴퓨터가 빠르게 풀 수 있는 문제들을 분석하는 데 쓸모가 있. 어떤 판정 문제가 P-완전이려면 P에 대해 완전해야.
보다 NP-완전와 P-완전
P-NP 문제
P는 NP에 속하지만, NP가 P에 속하는지 여부는 밝혀지지 않았다. P-NP 문제는 복잡도 종류 P와 NP가 같은지에 대한 컴퓨터 과학의 미해결 문제로 컴퓨터로 풀이법이 빠르게 확인된 문제가 컴퓨터로 빠르게 풀리기도 할 것인가 아닌가를 묻고 있.
PSPACE-완전
산 복잡도 이론에서 PSPACE-완전은 복잡도 종류이.
RE-완전
RE-완전은 복잡도 종류 RE에서 완전한 결정 문제의 집합이.
보다 NP-완전와 RE-완전
4색정리
색으로 칠한 지도의 예 4색정리(四色定理) 또는 4색문제(四色問題)는 평면을 유한 개의 부분으로 나누어 각 부분에 색을 칠할 때, 서로 맞닿은 부분을 다른 색으로 칠한다면 네 가지 색으로 충분하다는 정리이.
보다 NP-완전와 4색정리
또한 NP 완전, NP 완전 문제, NP-complete로 알려져 있다.