Open c-come opened 9 months ago
https://c-come.github.io/2023/10/31/%E3%80%90%E5%B0%8F%E7%9F%A5%E8%AF%86%E3%80%91%E5%AD%98%E5%9C%A8NTM%E6%98%8E%E7%A1%AE%E5%BF%AB%E4%BA%8EDTM%E7%9A%84%E5%A4%8D%E6%9D%82%E6%80%A7%E7%B1%BB%E5%90%97/
今天的计算理论课上，老师在讲NFA（非确定型有限自动机），然后就顺嘴提了一下以后要讲的NTM（非确定型图灵机）和DTM。他问：“NTM和DTM的计算能力一样吗？”（他指的是判定语言的能力）答案显然是一样的。他又问：“NTM和DTM的计算效率一样吗？”我脱口而出不一样，NTM更快。但又犹豫了。 老师说：“这个问题目前还不清楚，这就是P vs NP问题。” I mean, hold on…
https://c-come.github.io/2023/10/31/%E3%80%90%E5%B0%8F%E7%9F%A5%E8%AF%86%E3%80%91%E5%AD%98%E5%9C%A8NTM%E6%98%8E%E7%A1%AE%E5%BF%AB%E4%BA%8EDTM%E7%9A%84%E5%A4%8D%E6%9D%82%E6%80%A7%E7%B1%BB%E5%90%97/
今天的计算理论课上，老师在讲NFA（非确定型有限自动机），然后就顺嘴提了一下以后要讲的NTM（非确定型图灵机）和DTM。他问：“NTM和DTM的计算能力一样吗？”（他指的是判定语言的能力）答案显然是一样的。他又问：“NTM和DTM的计算效率一样吗？”我脱口而出不一样，NTM更快。但又犹豫了。 老师说：“这个问题目前还不清楚，这就是P vs NP问题。” I mean, hold on…