NP (복잡도)와 P-NP 문제의 유사점
NP (복잡도)와 P-NP 문제는 공통적으로 7 가지를 가지고 있습니다 (유니온백과에서): 부분집합, 비결정론적 튜링 기계, 다항 시간, 튜링 기계, NP-난해, NP-완전, P (복잡도).
부분집합
부분집합 관계를 표현한 벤 다이어그램. ''A''는 ''B''의 부분집합이다. 집합론에서 집합 B의 부분집합(部分集合) A는, 모든 원소가 B에도 속하는 집합이.
NP (복잡도)와 부분집합 · P-NP 문제와 부분집합 ·
비결정론적 튜링 기계
비결정론적 튜링 기계(nondeterministic Turing machine, NTM)는 튜링 기계에서 특정 상태에서 움직일 수 있는 상태의 개수가 하나로 정해져 있지 않은 경우를 말. 이것은 비결정론적 유한 오토마타와 유사한 개념이.
NP (복잡도)와 비결정론적 튜링 기계 · P-NP 문제와 비결정론적 튜링 기계 ·
다항 시간
항 시간(多項時間)은 어떠한 문제를 계산하는 데에 걸리는 시간 m(n)이 문제의 크기 n의 다항식 함수보다 크지 않은 것을 가리.
NP (복잡도)와 다항 시간 · P-NP 문제와 다항 시간 ·
튜링 기계
링 기계의 작동 방식을 묘사하는 그림 이론 전산학에서, 튜링 기계()는 긴 테이프에 쓰여있는 여러 가지 기호들을 일정한 규칙에 따라 바꾸는 기계이.
NP (복잡도)와 튜링 기계 · P-NP 문제와 튜링 기계 ·
NP-난해
NP-난해, NP-hard는 NP에 속하는 모든 판정 문제를 다항 시간에 다대일 환산할 수 있는 문제들의 집합이.
NP (복잡도)와 NP-난해 · NP-난해와 P-NP 문제 ·
NP-완전
NP-완전(NP-complete, NP-C, NPC)은 NP 집합에 속하는 결정 문제 중에서 가장 어려운 문제의 부분집합으로, 모든 NP 문제를 다항 시간 내에 NP-완전 문제로 환산할 수 있. NP-완전 문제 중 하나라도 P에 속한다는 것을 증명한다면 모든 NP 문제가 P에 속하기 때문에, P-NP 문제가 P.
NP (복잡도)와 NP-완전 · NP-완전와 P-NP 문제 ·
P (복잡도)
P(PTIME 또는 DTIME(nO(1)))는 결정론적 튜링 기계로 다항 시간 안에 풀 수 있는 판정 문제를 모아 놓은 복잡도 종류이.
위의 목록은 다음 질문에 대한 대답입니다
- NP (복잡도)와 P-NP 문제에는 공통점이 있습니다
- NP (복잡도)와 P-NP 문제의 유사점은 무엇입니까
NP (복잡도)와 P-NP 문제의 비교.
NP (복잡도)에는 10 개의 관계가 있고 P-NP 문제에는 24 개의 관계가 있습니다. 그들은 공통점 7을 가지고 있기 때문에, Jaccard 지수는 20.59%입니다 = 7 / (10 + 24).
참고 문헌
이 기사에서는 NP (복잡도)와 P-NP 문제의 관계를 보여줍니다. 정보가 추출 된 각 기사에 액세스하려면 다음 사이트를 방문하십시오: