「P1がP2に縮小されている場合、P2は少なくともP1と同じくらい難しい」とはどういう意味ですか？

Question

チューリング削減に関する次の声明を理解するのに問題がある：

「P1がP2に還元されると、P2は少なくともP1と同じくらい硬い。 "

これはその意味を意味します

（i）P2は、P1と同じくらい困難であるか、 （ii）P2は、P1の場合、またはP1のように硬いか難しいことができますか？

この視覚的に表現する...

問題についての洞察を感謝するだろう。ありがとうございました。

Answer 1

解釈（i）は正しいです。 " $ A $ は少なくとも $ b $ "" " $ a $ は $ b $ よりも厳密か厳密に難しいことを意味します。（数字について考えてください： " $ A $ は少なくとも $ b $ "という意味です " $ a= b $ または $ a> b $ "）

$ A $ は、少なくとも $ b $ のように難しいことです。ルールアウト $ a $ は $ b $ よりも厳密に弱くなるため、 $ A $ と $ b $ 非コンパイル不可能な複雑さ。複雑さは線形順ではありません。どちらも私たちがもう一方を解くのを助けないような問題を見つけることができます。