구현하기가 너무 어려운 강력한 알고리즘 – 올바른지 확인하는 방법? 이러한 복잡한 알고리즘에는 버그가 포함되어 알고리즘을 무효화

여기서 질문을 참조하고 있습니다 : 강력한 알고리즘이 너무 복잡하여 구현할 수 없습니다 .

알고리즘이 강력하지만 구현하기에 너무 복잡한 경우 알고리즘이 올바른지 어떻게 확인할 수 있습니까? 구현하지 않으면 실제 시나리오에서 알고리즘을 테스트 할 수 없으며 이러한 복잡한 알고리즘에는 버그가 포함되어 알고리즘을 무효화 할 수 있습니다.

이것이 내가 이해하지 못하는 것입니다. 알고리즘의 정확성을 입증 할 수있는 기술이 있다면 이미 구현할 알고리즘이 있습니까? 아니면 증명 기술이 올바른지 어떻게 확인할 수 있습니까?

초등하게 들리면 미안 해요!

Kaveh에서 업데이트 (논쟁이 더 좋기 때문에 여기에서 재현 됨) :

Coq와 같은 공식 시스템에서 알고리즘의 정확성을 공식적으로 증명할 수 있다면 알고리즘을 추출 할 수도 있지만 (기본적으로 알고리즘을 구현했기 때문에) 대부분의 알고리즘에 대해서는 공식적인 증거를 제공하지 않습니다. 알고리즘의 정확성에 대한 비공식적 인 정확성 증명을 사용합니다. 증명은 때때로 거짓이 될 수 있으며 공식적인 정확성 증명조차도 알고리즘이 올바른지 절대적으로 확신 할 수는 없습니다.



답변

몇 년 전에 이와 비슷한 주제에 대해 (거의 가혹한) 논쟁이있었습니다. 여러 복잡한 증명이 틀린 것으로 밝혀 졌을 때 모든 것이 시작되었고 일부 연구자들은 증명의 본질에 대해 의문을 제기하기 시작했습니다. . 논쟁의 양쪽은 상대방이 개념을 오해했다고 비난했다. 자세한 정보는 다음 링크를 참조하십시오 .

증명은 정리 / 알고리즘이 올바른지 증명하기위한 (수학적) 도구이지만, 너무 복잡해지면 잘못된 것이 잘못 될 수 있습니다. P ≠ NP에 대한 최근 100 페이지 또는 그 이상의 페이지 교정 이 훌륭한 예입니다. 그러나 이것이 증거의 본질을 배제하는 것은 아닙니다. 아무런 문제가 없습니다.

마지막 요점 : 과학 철학을 연구 하면 이에 대한 더 많은 통찰력을 얻을 수 있다고 생각 합니다. (주어진 링크 아래에서 ” 수학적 증거가 정확한지 어떻게 알 수 있습니까? ” 글 머리 기호 참조 )