컴퓨터 과학에는 아직 해결책을 찾지 못한 몇 가지 문제가 있으며, 문제는 다음과 같은 클래스로 나뉩니다. 복잡성 클래스 . 복잡성 이론에서 복잡성 클래스는 관련 복잡성을 갖는 문제 집합입니다. 이 수업은 과학자들이 문제를 해결하고 솔루션을 확인하는 데 필요한 시간과 공간을 기준으로 문제를 그룹화하는 데 도움이 됩니다. 문제를 해결하는 데 필요한 자원을 다루는 계산 이론의 한 분야입니다.

자바 시각화 장치

공통 자원은 시간과 공간이며, 이는 알고리즘이 문제를 해결하는 데 걸리는 시간과 그에 따른 메모리 사용량을 의미합니다.

• 알고리즘의 시간 복잡도는 문제를 해결하는 데 필요한 단계 수를 설명하는 데 사용되지만 답을 확인하는 데 걸리는 시간을 설명하는 데에도 사용할 수 있습니다.
• 알고리즘의 공간 복잡도는 알고리즘이 작동하는 데 필요한 메모리 양을 나타냅니다.

복잡성 클래스는 유사한 유형의 문제를 구성하는 데 유용합니다.

복잡성 클래스의 유형

이 문서에서는 다음 복잡성 클래스에 대해 설명합니다.

1. P 클래스
2. NP 클래스
3. CoNP 클래스
4. NP-하드
5. NP-완전

P 클래스

P 클래스의 P는 다음을 의미합니다. 다항식 시간. 다항식 시간 내에 결정론적 기계로 풀 수 있는 결정 문제(예 또는 아니오로 대답하는 문제)의 모음입니다.

특징:

• 해결 방법 P 문제 s는 찾기 쉽습니다.
• 피 종종 해결 가능하고 다루기 쉬운 계산 문제 클래스입니다. 다루기 쉽다는 것은 문제가 이론적으로나 실제로 해결될 수 있다는 것을 의미합니다. 그러나 이론상으로는 해결할 수 있지만 실제로는 해결할 수 없는 문제를 다루기 힘든 문제라고 합니다.

이 수업에는 많은 문제가 있습니다.

1. 최대 공약수를 계산합니다.
2. 최대 일치를 찾는 중입니다.
3. 병합 정렬

NP 클래스

NP 클래스의 NP는 다음을 나타냅니다. 비결정적 다항식 시간 . 다항식 시간 내에 비결정적 기계로 풀 수 있는 결정 문제의 모음입니다.

특징:

• NP 클래스의 해는 비결정적 기계로 풀기 때문에 찾기가 어렵지만 해를 검증하는 것은 쉽습니다.
• NP 문제는 튜링 기계를 사용하여 다항식 시간에 검증할 수 있습니다.

예:

자바와 스윙

더 잘 이해하기 위해 예를 들어 보겠습니다. NP 클래스 . 총 매출을 올리는 회사가 있다고 가정해 보겠습니다. 1000 고유한 직원이 있는 직원 ID . 있다고 가정 200 사용할 수 있는 객실이 있습니다. 다음의 선택 200 직원들은 반드시 짝을 이뤄야 하는데 회사 대표가 개인적인 사정으로 같은 공간에서 일할 수 없는 일부 직원들의 데이터를 갖고 있다.
이는 다음의 예입니다. 예 문제. 선택한 항목이 맞는지 쉽게 확인할 수 있기 때문에 200 동료가 제안한 직원이 만족스럽거나 그렇지 않습니다. 즉, 동료 목록에서 가져온 쌍이 CEO가 제공한 목록에 나타나지 않습니다. 그러나 그러한 목록을 처음부터 생성하는 것은 너무 어려워서 완전히 비현실적인 것 같습니다.

누군가가 문제에 대한 해결책을 제공할 수 있다면 다항식 시간 내에 올바른 쌍과 잘못된 쌍을 찾을 수 있음을 나타냅니다. 따라서 예 클래스 문제의 경우 다항식 시간으로 계산할 수 있는 답이 가능합니다.

이 수업에는 효과적으로 해결하고 싶은 많은 문제가 포함되어 있습니다.

1. 부울 만족도 문제(SAT).
2. 해밀턴 경로 문제.
3. 그래프 채색.

공동NP클래스

Co-NP는 NP Class를 보완한 것을 의미합니다. Co-NP의 문제에 대한 답이 No라면 다항식 시간에 확인할 수 있는 증명이 있다는 의미입니다.

특징:

힙 정렬 알고리즘

• 문제 X가 NP에 있으면 그 보완 X'도 CoNP에 있습니다.
• NP 및 CoNP 문제의 경우 다항식 시간에 모든 답변을 한 번에 확인할 필요가 없으며 문제가 NP 또는 CoNP에 있으려면 다항식 시간에 예 또는 아니요라는 특정 답변 하나만 확인하면 됩니다.

CoNP의 몇 가지 문제 예는 다음과 같습니다.

1. 소수를 확인하려면.
2. 정수 인수분해.

NP-하드 클래스

NP-하드 문제는 최소한 NP의 가장 어려운 문제만큼 어렵고 NP의 모든 문제가 NP-하드로 축소되는 문제 유형입니다.

특징:

• 모든 NP-하드 문제는 NP에 있지 않습니다.
• 확인하는 데 시간이 오래 걸립니다. 이는 NP-하드 문제에 대한 해결책이 제공되면 그것이 올바른지 여부를 확인하는 데 오랜 시간이 걸린다는 것을 의미합니다.
• NP의 모든 문제 L에 대해 L에서 A로의 다항식 시간 감소가 존재하는 경우 문제 A는 NP-hard입니다.

Np-hard 문제의 몇 가지 예는 다음과 같습니다.

1. 정지 문제.
2. 정규화된 부울 수식.
3. 해밀턴 사이클이 없습니다.

NP 완전수업

문제는 NP와 NP-하드 모두인 경우 NP-완전입니다. NP-완전 문제는 NP의 어려운 문제입니다.

특징:

• NP-완전 문제는 NP 클래스의 모든 문제가 다항식 시간 내에 NP-완전 문제로 변환되거나 축소될 수 있다는 점에서 특별합니다.
• 다항식 시간에 NP-완전 문제를 풀 수 있다면 다항식 시간에 모든 NP 문제도 풀 수 있습니다.

몇 가지 문제 예는 다음과 같습니다.

1. 해밀턴 사이클.
2. 만족감.
3. 정점 커버 .