다항식 시간 : 수락 및 의사 결정 알고리즘

Question

수락 및 의사 결정 알고리즘을 구별 할 수없는 것처럼 보입니다. 개념을 이해하고있는 것 같지만. 이 같은 튜링의 앞뒤가 맞지 문제와 같은 다른 문제에 대해서는

는 "받아들이는 알고리즘이 존재한다고 나는 현재, 장 NP-완전성 다음"알고리즘 소개 "(Cormen을) 읽기, 문제가 있어요 결정 알고리즘은 존재하지 않습니다. "

이 나에게이 시점까지 감지 할 않지만, 우리는 더 나아가 말

"P= {L from {0,1}*: there exists an algorithm A that decides L in polynomial time} 

그 그리고 우리는 P는 것을 증명하려는

P={L:L is accepted by a polynomial time algorithm}, starting with 

"언어 클래스가 다항식 - 시간 알고리즘에 의해 결정 되었기 때문에, L이 다항식 - 시간 알고리즘에 의해 받아 들여지면 다항식 - 시간 알고리즘에 의해 결정된다는 것을 보여줄 필요가 있습니다."

그런 다음 수락 알고리즘의 시뮬레이션을 구성하여 수락 알고리즘의 동작을 추가로 검사하고 이전 알고리즘이 입력을 수락하면 1을 출력하고 그렇지 않으면 0을 출력합니다.

그런 알고리즘을 만들 수 있다면 정지 문제에는 수락 알고리즘이 있지만 결정 알고리즘이 아닌 것은 어떻게 가능합니까?

Answer 1

차이점은 런타임의 상한과 관련이 있습니다. 다항식 시간 알고리즘을 고려할 때 당신이 다항식 시간 수용체가있는 경우 다음과 같이, 당신은 다항식 시간 결정자으로 바꿀 수 있습니다

• 이가 걸릴 시간의 다항식 시간 동안 알고리즘 을 실행 최악의 경우 받아 들인다.
• 이번에 받아 들여지면 멋지다! 동의하십시오.
• 이 시간에 동의하지 않으면 절대로 받아 들여지지 않을 것입니다. 받지 않다.

따라서, 액서서는 결정자로 바뀔 수 있습니다.

지금, 앞뒤가 맞지 않는 문제에 대한 같은 일에 대해 생각 :

• 만큼이 최악의 경우에 수용하기 위해 수행하는 것처럼 알고리즘 를 실행합니다.
• 이번에 받아 들여지면 멋지다! 동의하십시오.
• 이 시간에 동의하지 않으면 절대로 받아 들여지지 않을 것입니다. 받지 않다.

여기서 문제는 알고리즘이 수용 할 수있는 고정 된 시간이 없다는 것입니다. 프로그램은 수락하기 전에 임의로 실행될 수 있기 때문에 "이미 수락 할 때까지 실행하십시오. "시간이 얼마인지 알아낼 수있는 계산 과정이 없기 때문에.

흥미롭게도이 기능은 비지 비지 기능에 연결됩니다.크기가 n 인 busy-beaver는 직관적으로 항상 길이가 n 인 프로그램으로, 항상 멈추지 만 크기 n의 모든 프로그램에서 중단 될 수있는 가장 오랜 시간이 걸립니다. 특정 입력 w에 대해, 차수 n의 w에 대한 비지 비버 수는 크기 n의 비지 비버 프로그램이 입력 w에서 정지하는 단계의 수이다. 이 숫자는 수학적으로 잘 정의되어 있지만 컴퓨터 프로그램이나 다른 방법으로는 계산할 수 없으며 위 알고리즘을 올바르게 사용할 수 있습니다.

희망이 도움이됩니다.