검수요청.png검수요청.png

여 NP-완전

위키원
(여NP완전에서 넘어옴)
이동: 둘러보기, 검색

여 NP-완전(co-NP-complete)은 여 NP에서 가장 어려운 문제의 집합을 말한다. 여기서 어렵다는 것은, P에 들어갈 가능성이 낮다는 뜻이다. 한 여 NP-완전 문제를 빠르게 푸는 방법을 찾아낸다면, 그 방법을 써서 모든 여 NP-완전 문제를 빠르게 풀 수 있게 된다.

정의[편집]

결정 문제 가 여 NP에 속하며, 모든 여 NP 문제를 로 다항 시간 내에 변환할 수 있다면, C는 여 NP-완전이라고 한다. 이는 모든 여 NP 문제 에 대해, 에 대한 예제를 에 대한 예제로 변환할 수 있는 다항 시간 알고리즘이 존재함을 의미한다. 따라서 를 다항 시간 내에 해결할 수 있는 알고리즘이 있다면, 모든 여 NP 문제를 다항 시간 내에 해결할 수 있게 된다.

대표적인 여 NP-완전 문제로는 항진 명제 문제가 있다. 이는 주어진 논리식이 모든 변수 값의 조합에 대해 항상 참인지 판별하는 문제이다. 즉, 변수에 참 또는 거짓 값을 어떤 방식으로 대입하더라도 논리식 전체가 참이 되어야 한다. 이 문제는 불만족성 문제와 밀접한 관련이 있다. 불만족성 문제는 논리식이 참이 되는 변수값 할당이 존재하는지를 판별하는 문제인 반면, 항진 명제 문제는 모든 변수값 할당에 대해 논리식이 참이 되는지를 묻는다.

여 NP-완전 문제들은 NP-완전 문제의 보완 문제로 간주될 수 있다. 여 NP-완전과 NP-완전은 동일한 집합일 수도 있고, 전혀 겹치지 않는 집합일 수도 있다. 후자의 가능성이 더 유력하다고 여겨지지만, 현재로서는 확정된 바는 없다.[1]

관계[편집]

여 NP[편집]

여 NP는 결정 문제의 복잡도 클래스다. 여기서 문제의 해답이 '아니오'일 때, 그 증명 과정이 다항 시간 내에 검증 가능한 문제들을 포함한다. 다시 말해, 여 NP에 속하는 문제들은 주어진 해답이 틀렸다는 것을 효율적으로 확인할 수 있는 문제들이다.

여 NP-완전 문제는 여 NP 클래스의 문제들 중에서 가장 어려운 문제들을 말한다. 구체적으로, 문제 가 여 NP-완전이 되기 위한 조건은 다음과 같다.

  • 문제 가 여 NP에 속해야 한다.
  • 모든 여 NP 문제는 문제 로 다항 시간 내에 변환 가능해야 한다.

즉, 여 NP-완전 문제는 여 NP 클래스의 모든 문제를 다항 시간 내에 변환할 수 있는 문제이며, 따라서 여 NP 문제를 해결할 수 있는 다항 시간 알고리즘이 있다면, 여 NP-완전 문제를 해결할 수 있는 알고리즘도 존재한다고 할 수 있다.

NP-완전[편집]

  • NP-완전(NP-complete) 문제는 NP 클래스의 문제들 중 가장 어려운 문제들이다. NP-완전 문제는 NP 문제를 다항 시간 내에 변환할 수 있는 문제들이다.
  • 여 NP-완전 문제와 NP-완전 문제는 서로 보완적인 관계에 있다. 즉, NP-완전 문제의 보완 문제가 여 NP-완전 문제로 간주될 수 있다. 두 클래스가 동일한지, 혹은 전혀 겹치지 않는지는 현재까지 확실하지 않으며, 이는 복잡도 이론의 중요한 미해결 문제 중 하나다.

따라서, 여 NP-완전 문제는 여 NP 클래스에서 가장 어려운 문제들을 나타내며, 이 문제들이 효율적으로 해결될 수 있는 알고리즘이 존재한다면, 모든 여 NP 문제를 효율적으로 해결할 수 있는 가능성이 생긴다.

각주[편집]

  1. co-NP-완전〉, 《위키백과》

참고자료[편집]

같이 보기[편집]


  검수요청.png검수요청.png 이 여 NP-완전 문서는 인공지능 기술에 관한 글로서 검토가 필요합니다. 위키 문서는 누구든지 자유롭게 편집할 수 있습니다. [편집]을 눌러 문서 내용을 검토·수정해 주세요.