2014-09-16 3 views
1

여러 변수의 실제 함수의 0을 찾고 싶습니다. Newton-Rhapson 메서드와 같은 많은 알고리즘이이 문제를 해결하는 것으로 알려져 있지만 일반적으로 이러한 문제는 NP 완전 클래스 문제에 속해 있습니까? 변수의 수가 많으면 합리적인 시간에이를 해결하는 방법을 알고 있습니까?함수의 0이 NP-pb입니까?

미리 감사드립니다.

추신 : 나는이 질문을 포럼에서 물어 보지 못했지만 일부 주제는 밀접하게 관련되어있는 것으로 보입니다. 제 질문이 중복되면 제게 말해주십시오.

답변

0

입력 정의 란 무엇입니까? 복잡성에 대한 질문은 실행 시간을 입력의 인코딩 길이와 비교해야한다는 것을 기억하십시오.

그리고 컴퓨터 용어로 "솔루션"으로 무엇을 이해합니까? 하나의 유한 정의는 합리적인 모서리를 가진 상자가 정확히 하나의 솔루션을 포함합니다. 또는 Newtons 방법의 2 차 수렴 도메인 내부의 비슷한 상자. Blum/Shucker/Smale /의 표준 책을 보시오 ?? 실수의 복잡성에 대해

다항식 문제의 경우에도 상황은 복잡하며 다항식 시스템의 해가 P인지 NP인지는 알 수 없습니다.