비 결정적 프로 시저 란 무엇입니까?

Question

문제가 있습니다 ... 비결정 절차가 무엇입니까? 내가 Indipendent 설정 s.t.했다 G = (V, E) : L = {: 나는이 운동

은 다음 언어에 대한 결정적 절차를 제공해야 | 나는 | > = k이고 정점 V_1은 해밀턴 사이클을 형성 함}

고마워!

Answer 1

비 결정적 프로 시저 또는 함수는 주어진 입력 값에 대해 이 아닌이 항상 동일한 출력을 생성하는 프로 시저입니다.

예 : DateTime.GetCurrent는 비 결정적입니다. Random.Next()는 비 결정적입니다. Math.Sin()은 결정적 일 수 있기를 바랍니다. 동일한 값을 10 회 입력하면 같은 결과가 10 번 나타납니다.

Answer 2

비 결정적 함수는 "오라클"에 의존 할 수 있습니다. 귀하의 예제에서 오라클은 I 집합을 생성 할 것이고 함수는 특정 속성 (예 : I)이 독립적인지 확인해야하며 |I| >= k 및 V\I은 해밀턴주기를 형성합니다.