谁能给我一个证明，证明 K-Complexity 是无法使用约简解决的。
例如：
PCP(2) <= PCP(3)
我可以通过简化为 PCP(2)（通过映射每个实例）来证明 PCP(3) 是不可解的。
我不确定如何将 K-Complexity 减少为另一个已知的不可判定问题（如停止问题）。即，X <= K-复杂度
你能给我证明吗？至少给我一些想法（X）。
提前致谢
问问题
155 次
谁能给我一个证明，证明 K-Complexity 是无法使用约简解决的。
例如：
PCP(2) <= PCP(3)
我可以通过简化为 PCP(2)（通过映射每个实例）来证明 PCP(3) 是不可解的。
我不确定如何将 K-Complexity 减少为另一个已知的不可判定问题（如停止问题）。即，X <= K-复杂度
你能给我证明吗？至少给我一些想法（X）。
提前致谢