둘러보기 메뉴
검색
바뀐글
임의글
개인 도구
가입하기
로그인
도움말
도움말
질문게시판
자주 묻는 질문
커뮤니티
실시간 채팅방
가입인사게시판
자유게시판
뉴스게시판
제재안게시판
최근 토론
페미위키
공지사항
개선 요청
바뀐글
임의글
파일 올리기
다면 분류 목록
특수 문서 목록
P-NP 문제 문서 원본 보기
이름공간
문서
토론
주시
도구
여기를 가리키는 문서
가리키는 글의 최근 바뀜
문서 정보
위키베이스 항목
행위
보기
읽기
원본 보기
역사 보기
←
P-NP 문제
문서 편집 권한이 없습니다. 다음 이유를 확인해주세요.
요청한 명령은 다음 중 하나의 권한을 가진 사용자에게 제한됩니다:
사용자
,
Seeders
.
문서를 고치려면 이메일 인증 절차가 필요합니다.
사용자 환경 설정
에서 이메일 주소를 입력하고 이메일 주소 인증을 해주시기 바랍니다.
문서의 원본을 보거나 복사할 수 있습니다.
[[P-NP 문제]]는 [[복잡도 종류]] [[P 집합]]과 [[NP 집합]]이 같은지에 대한 컴퓨터 과학의 미해결 문제이다. ==개요== [[P]]([[PTIME]] 또는 [[DTIME]])는 [[결정론적 튜링 기계]]로 [[다항 시간]] 안에 풀 수 있는 [[판정 문제]]를 모아 놓은 [[집합]]이다. [[NP]]는 [[비결정론적 튜링 기계]]로 [[다항 시간]] 안에 풀 수 있는 [[판정 문제]]들의 집합으로, 이 문제들은 결정론적 튜링 기계로 다항 시간 안에 답을 검증할 수 있다. 즉 '''P는 NP의 [[부분집합]]'''이다. 그러나 P=NP인지, 즉 '''NP 역시 P의 부분집합인지는 아직 알려지지 않았다.''' 이에 대한 문제를 [[P-NP 문제]]라고 한다. [[1971년]] [[미국]]의 [[전산학자]]인 [[스티븐 쿡]]이 그의 논문 〈The Complexity of Theorem Proving Procedures{{주|정리 증명 절차의 복잡성}}>에서 처음 제안하였고, 그보다 더 전에는 [[1956년]] [[수학자]]이자 [[논리학자]]인 [[쿠르트 괴델]]이 [[폰 노이만]]에게 썼던 편지에서 처음으로 언급되었다. 괴델은 어떤 NP 완전 문제가 [[2차 시간]] 혹은 [[선형 시간]] 안에 풀릴 수 있는지를 물었다. [[밀레니엄 문제]] 중 하나이다. ==부연 설명== {{부연 설명}} [[분류:분야/수학]] [[분류:성격/밀레니엄 문제]]
이 문서에서 사용한 틀:
틀:부연 설명
(
원본 보기
)
틀:주
(
원본 보기
)
P-NP 문제
문서로 돌아갑니다.
다른 언어