NP-Easy

복잡성 이론에서, 복잡성 등급 NP-easy는 NP의 일부 의사결정 문제에 대해 오라클이 있는 비계수적 튜링 기계에 의해 다항 시간 내에 해결할 수 있는 기능 문제의 집합이다.

즉, 문제 X는 다항 시간 튜링이 Y로 환원될 수 있도록 NP에 어떤 문제 Y가 존재하는 경우에만 NP가 쉽다.^[1]즉, Y에 대한 신탁이 주어지면 다항 시간(아마도 그 신탁을 반복적으로 사용함으로써)에 X를 해결하는 알고리즘이 존재한다는 것을 의미한다.

NP-easy는 FP^NP(함수 문제 기사 참조) 또는 FΔP₂(다항식 계층 구조 기사 참조)의 다른 이름이다.

NP-편리한 문제의 예는 문자열 목록을 정렬하는 문제다.의사결정 문제 "A 문자열 B보다 큰가"는 NP에 있다.비교 루틴에 대한 다항식 호출 수만을 사용하여 목록을 정렬할 수 있는 퀵소트 같은 알고리즘과 더불어 추가 작업의 다항식량도 있다.따라서 정렬은 NP-편리하다.

또한 NP-편리한 더 어려운 문제들이 있다.예를 보려면 NP 등가 항목을 참조하십시오.

NP-easy의 정의는 문제 Y에 대한 해답은 TRUE 또는 FALSE일 뿐 문제 X에 대한 해답은 더 일반적일 수 있기 때문에 다수 1의 감소보다는 튜링 감소를 사용한다.따라서 X의 인스턴스(instance)를 같은 해답을 가진 Y의 인스턴스(instance)로 번역할 수 있는 일반적인 방법은 없다.

메모들

참조

• Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, ISBN 0-7167-1045-5.