브라우저보다 빠른!
14 처지: 결정 문제, 부분집합 합 문제, 튜링 기계, 정지 문제, 집합, 충족 가능성 문제, 최적화 문제, 서로소 집합, 함수 문제, 신탁 기계, 환산 (복잡도), NP (복잡도), NP-완전, P-NP 문제.
결정 문제
산 이론에서 결정 문제(decision problem, 판정 문제)란 어떤 형식 체계에서 예-아니오 답이 있는 질문을 말..
새로운!!: NP-난해와 결정 문제 · 더보기 »
부분집합 합 문제
부분집합 합 문제(subset sum problem)는 계산 복잡도 이론과 암호학에 관련된 문제로, 유한 개의 정수로 이루어진 집합이 있을 때 이 집합의 부분집합 중에서 그 집합의 원소를 다 더한 값이 0이 되는 경우가 있는지를 알아내는 문제이.
새로운!!: NP-난해와 부분집합 합 문제 · 더보기 »
튜링 기계
링 기계의 작동 방식을 묘사하는 그림 이론 전산학에서, 튜링 기계()는 긴 테이프에 쓰여있는 여러 가지 기호들을 일정한 규칙에 따라 바꾸는 기계이.
새로운!!: NP-난해와 튜링 기계 · 더보기 »
정지 문제
산 복잡도 이론에서 정지문제(停止問題, halting problem)는 판정 문제의 일종으로 다음과 같이 요약할 수 있. 1936년에 앨런 튜링이 모든 가능한 입력값에 대해 정지문제를 풀 수 있는 일반적인 알고리즘 은 존재하지 않는다는 것을 증명.
새로운!!: NP-난해와 정지 문제 · 더보기 »
집합
9개의 다각형의 집합을 나타낸 오일러 다이어그램 수학에서, 집합(集合)은 명확한 기준에 의하여 주어진 서로 다른 대상들이 모여 이루는 새로운 대상이.
충족 가능성 문제
충족 가능성 문제(充足可能性問題, satisfiability problem, SAT)는 어떠한 변수들로 이루어진 논리식이 주어졌을 때, 그 논리식이 참이 되는 변수값이 존재하는지를 찾는 문제이.
새로운!!: NP-난해와 충족 가능성 문제 · 더보기 »
최적화 문제
적화 문제는 수학 혹은 컴퓨터 과학에서 모든 테스트 케이스에 대해 답을 찾는 최적의 해법을 찾는 문제를 말. 분류:계산 문제.
새로운!!: NP-난해와 최적화 문제 · 더보기 »
서로소 집합
서로소인 두 집합 집합론에서, 서로소 집합(-素集合)는 공통 원소가 없는 두 집합이.
새로운!!: NP-난해와 서로소 집합 · 더보기 »
함수 문제
산 복잡도 이론에서 함수 문제란 판정 문제가 아닌 문제들, 다시 말해서 답이 예/아니오보다 복잡한 문제들이.
새로운!!: NP-난해와 함수 문제 · 더보기 »
신탁 기계
신탁 기계(神託機械, oracle machine)는 판정 문제를 연구하는 데 사용하는 추상 기계로, 일반적인 튜링 기계에 '신탁'(神託, oracle)이라는 블랙박스를 붙여놓은 것이라고 생각할 수 있. 이때 신탁은 어떤 판정문제를 단 한번의 동작으로 풀 수 있는 장치이.
새로운!!: NP-난해와 신탁 기계 · 더보기 »
환산 (복잡도)
복잡도 이론과 계산 복잡도 이론에서 환산(reduction)은 어떤 문제를 다른 문제로 변형하는 과정이.
새로운!!: NP-난해와 환산 (복잡도) · 더보기 »
NP (복잡도)
NP는 비결정론적 튜링 기계(NTM)로 다항 시간 안에 풀 수 있는 판정 문제의 집합으로, NP는 비결정론적 다항시간(非決定論的 多項時間, Non-deterministic Polynomial time)의 약자이.
새로운!!: NP-난해와 NP (복잡도) · 더보기 »
NP-완전
NP-완전(NP-complete, NP-C, NPC)은 NP 집합에 속하는 결정 문제 중에서 가장 어려운 문제의 부분집합으로, 모든 NP 문제를 다항 시간 내에 NP-완전 문제로 환산할 수 있. NP-완전 문제 중 하나라도 P에 속한다는 것을 증명한다면 모든 NP 문제가 P에 속하기 때문에, P-NP 문제가 P.
새로운!!: NP-난해와 NP-완전 · 더보기 »
P-NP 문제
P는 NP에 속하지만, NP가 P에 속하는지 여부는 밝혀지지 않았다. P-NP 문제는 복잡도 종류 P와 NP가 같은지에 대한 컴퓨터 과학의 미해결 문제로 컴퓨터로 풀이법이 빠르게 확인된 문제가 컴퓨터로 빠르게 풀리기도 할 것인가 아닌가를 묻고 있. 1971년 스티븐 쿡이 그의 논문 〈The Complexity of Theorem Proving Procedures〉(정리 증명 절차의 복잡성)에서 처음으로 제안하였고 클레이 수학연구소에서 발표한 7개의 '밀레니엄 문제' 중 하나이며 컴퓨터 과학에서 중요한 위치를 차지하고 있. 이것은 본래 1956년 쿠르트 괴델이 존 폰 노이만에게 썼던 편지에서 처음으로 언급되었.
새로운!!: NP-난해와 P-NP 문제 · 더보기 »
