possibility / impossibility

undecidablity, incomputability, intractabilityの濃度の違い

ゲーデルの不可能性定理や、チューリングのhalting problemは当時undecidablityに関する定理だと思われていたが、NP completeなどの体系がクック、レビンらにより定理化されるにつれて、その決定…
Read more