P1이 P2로 줄어들면 P2가 적어도 P1이 적어도 딱딱한 것처럼 무엇을 의미합니까?

Question

Turing Reduction과 관련하여 다음 진술을 이해하는 데 어려움이 있습니다.

"P1이 P2로 감소하면 P2가 적어도 P1만큼 단단합니다."

이는

(i) P2는 P1만큼 열심히 또는 단단 할 수 있거나 (ii) P2는 쉽거나 P1만큼 열심히 할 수 있습니까?

이것을 시각적으로 표현 ...

>>

나는 그 문제에 대한 통찰력을 감사하게 될 것입니다.고맙습니다.

Answer 1

해석 (i)은 올바른 것입니다 : " $ a $ 은 적어도 $ b $ " $ a $ 은 $ b $ 보다 어렵거나 엄격하게 어렵습니다.( " $ a $ 은 적어도 $ b $ "만큼 크게 " $ a= b $ 또는 $ a> b $ ")

" $ a $ 은 적어도 $ b $ "만큼 열심히 할뿐만 아니라 $ a $ 은 $ b $ 보다 엄격하게 약하다. $ a $ 및 $ b $ 비교할 수없는 복잡성 입니다.복잡성은 선형 순서가 아닙니다.우리는 우리가 다른 사람을 해결할 수 있도록 도움이되지 않는 문제를 찾을 수 있습니다.