K-Complexity がリダクションを使用して解決できないことの証明を教えてください。
例えば：
PCP(2) <= PCP(3)
PCP(3) が解けないことは、PCP(2) に還元することで証明できます (すべてのインスタンスをマッピングすることにより)。
K-Complexity を別の既知の決定不能な問題 (停止問題など) に減らす方法がわかりません。つまり、X <= K-Complexity
その証拠を教えてください。少なくともアイデアを提供してください ( X )。
前もって感謝します