Np 는 무슨 뜻인가요?

NP 는 일반적으로 NP 전체 문제 (NP-C 문제) 를 나타냅니다.

그것은 세계 7 대 수학 문제 중 하나이다. NP 의 영어 전체 이름은 비 결정적 다항식의 완전한 문제, 즉 다항식 복잡성의 불확실성입니다. 간단한 표기법은 NP=P? 문제는 이 물음표에 있다. NP 가 P 와 같은지 아니면 NP 가 P 와 같지 않다.

일부 NP 문제의 복잡성은 전체 클래스의 복잡성과 관련이 있습니다. 이러한 문제 중 하나에 다항식 시간 알고리즘이 있는 경우 모든 NP 문제는 다항식 시간으로 해결할 수 있습니다. 이러한 문제를 NP 전체 문제 (NPC 문제) 라고 합니다.

확장 데이터:

NP 완전 문제의 예

어느 토요일 밤, 너는 성대한 모임에 참가했다. 어색해, 이 홀에 네가 이미 아는 사람이 있는지 알고 싶어. 너의 주인은 네가 디저트 접시 구석에 앉아 있는 로스 여사를 꼭 알 것을 건의한다.

너는 1 초도 걸리지 않고 그곳을 한 번 훑어보고, 너의 주인이 옳다는 것을 발견할 수 있다. 하지만 그러한 암시가 없다면, 홀 전체를 둘러보고, 모든 사람을 하나씩 살펴보고, 아는 사람이 있는지 확인해야 합니다.

문제를 생성하는 솔루션은 일반적으로 주어진 솔루션을 검증하는 것보다 시간이 더 많이 걸립니다. 이것은 이런 보편적인 현상의 한 예이다. 마찬가지로, 13, 717,42/Kloc-0

모든 완전한 다항식 불확실성 문제를 만족 문제라는 논리적 연산 문제로 변환할 수 있다는 것을 발견했습니다. 이런 종류의 질문에 가능한 모든 답은 다항식 시간 내에 계산될 수 있기 때문에, 사람들은 이런 문제의 확실성 알고리즘이 있는지 알고 싶어 다항식 시간 내에 직접 계산하거나 정답을 찾을 수 있다. 이것은 유명한 NP=P 입니까? 알아맞혀 보다. -응?

프로그램을 능숙하게 작성하든 안 하든, 답이 내부 지식으로 신속하게 검증될 수 있는지, 아니면 이런 힌트 없이 해결하는 데 많은 시간이 걸리든, 이것은 논리와 컴퓨터 과학에서 가장 두드러진 문제 중 하나로 여겨진다. 그것은 스티븐 코크가 197 1 에서 진술한 것이다.