HP 연구원이 Compsci 복잡성 문제를 해결했다고 주장

Hewlett-Packard 릴 마크 허드 (Mark Hurd) CEO의 퇴진에 따라 HP 연구원은 컴퓨터 과학에서 가장 어려운 문제 중 하나에 대한 해결책이라고 제안했다.

HP Labs의 수석 연구 과학자 인 Vinay Deolalikar는 P 대 NP 문제로 널리 알려진 것에 대한 해결책이라고 주장한 것을 게시했습니다.

Clay Mathematics Institute는 미국을 해결하는 사람에게 수여한다는이 문제를 다루기가 어렵습니다. 1 백만 달러. Millennium Prize Problems라고 일컬어지는 일곱 가지 문제 중 하나입니다. 연구소는이 현상금을 제공했습니다. 푸앵카레 추측의 7 개 중 하나가 2006 년에 공식적으로 해결되었습니다.

클레 레이는 문제가 해결되었다고 말하지 않았기 때문에 데놀라이카가 현금을 얻을 지 아직 확실하지 않습니다.

컴퓨터 과학의 현저한 문제는 "신속하게 답을 찾을 수 있지만 어떤 직접적인 절차로도 풀기에는 엄청나게 긴 시간이 걸리는 질문이 있는지 판단하는 것을 포함합니다"라고 연구소 페이지는 설명합니다. 문제에서 P는 다항식 시간을 의미하고 NP는 비 결정적 다항식 시간을 의미합니다. "Deolalikar는 P가 NP와 동등하지 않다는 증명을 발표하게되어 기쁘게 생각합니다."Deolalikar는 수학 교수 그룹에게 전자 메일로 알렸다. 브리티시 컬럼비아 주 사이먼 프레이저 대학 (British Columbia Simon Fraser University)의 선임 강사 인 그렉 베이커 (Greg Baker)는 일요일에 게시했습니다.

간단히 말해서, 이것은 문제가 브 루트 포스 검색을 통해서만 해결 될 수 있음을 의미합니다. "이 증거는 수학 분야의 여러 영역에서 나온 원칙을 결합 할 것을 요구했는데,이 증거를 구축하기위한 주요 노력은 다양한 분야 간의 개념적 연결 고리를 발견하고 공통 렌즈를 통해이를 보여주는 것이 었습니다."라고 Deolalikar는 말했습니다.

당연히이 문제에 익숙한 사람들은 Deolalikar가 수행해야 할 점검의 양을 고려할 때 문제를 해결했다고 선전하기를 주저합니다. Deolalikar는 자신의 철저한 접근 방식을 칭찬하지만, 일반적으로 제시되는 더 위험한 추측과는 다르다. 아무도 그 문제를 단호하게 주장한 사람은 없다.

"생각을 자극하는 새로운 아이디어, 특히 통계 물리학과 NP의 1 차 논리 특성화 사이의 연결 "이라고 매사추세츠 공과 대학의 전기 공학 및 컴퓨터 과학 조교수 인 스콧 아론 손 (Scott Aaronson)은 비공식적 인 블로그 엔트리에 글을 썼다.

지금 당장 생각하기를 바란다. 그러나 나는 확실히 희망적이다. "조지아 공과 대학 (Georgia Institute of Technology)의 컴퓨터 과학 교수 인 딕 립튼 (Dick Lipton)은 다음과 같이 덧붙였다.

Joab Jackson은 엔터프라이즈 소프트웨어 및 일반 기술 관련 뉴스를 다루고있다.

. @Joab_Jackson에서 Twitter의 Joab을 팔로우하십시오. Joab의 전자 메일 주소는 [email protected]입니다.