解析网友姜咏江的“k-CNF-SAT子句消去法”

热度 2 柳渝 2015-7-24 23:38

网友姜咏江提出“k-CNF-SAT子句消去法”，认为其算法的时间复杂度是“多项式时间”，从而一举解决了K－SAT问题。我们认为其中存在双重错误，一方面，模糊了“多项式时间”的“立场”，将多项式时间解决的“一维数组的搜索问题”（P）混淆为“K（K=3）－SAT问题”（NP）；另一方面，将解决若干K－SAT问题实例混淆为解决K ...

个人分类: 不确定性问题和算法讨论|3561 次阅读|9 个评论 热度 2

NP是可计算的吗？－ SAT问题

热度 3 柳渝 2015-7-17 16:14

目前为止，我们直接针对NP的流行定义：“NP是多项式时间可验证的问题”，解读其认知错误。我们指出，此认知错误来自于混淆了“nondeterministic Turing machine”二个不同的内涵：NTM（非图灵机）和NDTM（不确定性图灵机），从而得出NP二个定义等价，致NP的“不确定性”消失。 另外，还存在着一个更加令人困惑的流行观点 ...

个人分类: 不确定性问题和算法讨论|6189 次阅读|10 个评论 热度 3

传统定义的“非确定型图灵机”存在什么问题？——答网友

热度 1 柳渝 2015-7-6 13:16

迄今为止，传统定义的“非确定型图灵机”（NDTM），即我们称之的“不确定性图灵机”，存在的问题在于用NDTM定义的NP问题中没有了真正的“不确定性”，我们称之为“不确定性的消失”。NDTM以计算的“多选择”替代了问题本身的“不确定性”，肯定“可判定”就前提性地肯定了所定义的NP问题是P算法可判定的，所以我们认为流行 ...

个人分类: 不确定性问题和算法讨论|3880 次阅读|4 个评论 热度 1

法国高考“法语”笔试（理科，经济社会科，2014年）

热度 1 柳渝 2015-7-5 17:21

大家一直在议论法国高考“哲学”，并将之与中国的高考作文相比较，实际上，中国的高考作文是“语文”考试的题目，而法国的“哲学”课可比之于中国的“政治”课，“法语”课才相当于中国的“语文”课，所以，若作比较，还应看看法国高考“法语”。就培养、锻炼学生的分析和判断能力而言，法国的“法语”课与“哲学”课有互 ...

个人分类: 在中法文化之间流连|3718 次阅读|1 个评论 热度 1

对NP的误导和对NP的误解

热度 2 柳渝 2015-7-1 21:30

“P versus NP”成为世纪难题原因复杂。在理论上，专业学者混淆了P和NP的层次，将NP定义为“Non-deterministic Polynomial time，不确定性多项式时间）”，导致NP的本质“不确定性”的消失，此误导可追溯到Cook定理。 而一般对“P versus NP”感兴趣的大众学者，由于缺乏对NP与P的形式化定义的深入了解，往往以数学中 ...

个人分类: 不确定性问题和算法讨论|3460 次阅读|10 个评论 热度 2

法国高中哲学课程

柳渝 2015-6-30 19:01

女儿今年上高三，我对他们的哲学教科书“思想的道路（Le Chemin de la pensée - Philosophie Terminales L-ES-S (Edition 2012)，Jacqueline Russ, Clotilde Leguil）”略作介绍，以助大家进一步了解法国高中哲学课。 法国哲学课设在高三，每周文科和经济社会科学生有8小时、理科学生有4小时的课时，课时和课程设置均由 ...

个人分类: 在中法文化之间流连|6571 次阅读|没有评论

法国今年（2015）高考哲学第一题的答案提示

热度 6 柳渝 2015-6-25 17:46

法国高考哲学并非外人想象的任性，而是有类似中国科举八股文套路的。一般来说，法国的会考与中国的科举有历史渊源，。。。 法国高中的哲学课程教给学生们分析、论证问题的方法，其答题需从古希腊到现代的著名哲学家的著作中引经据典论述，学生大都不可能真正理解这些经典论述，但若大体上掌握了分析、论证问题的方法，一 ...

个人分类: 在中法文化之间流连|7294 次阅读|7 个评论 热度 6

法国今年（2015）高考哲学作文

热度 12 柳渝 2015-6-17 23:00

法国高三有一门高强度的哲学课，对此哲学课的评价，我常听到法国人和中国人持相当不同的观点：一边，不少法国人、法国学生抱怨哲学课的艰涩、难懂、与日常生活脱节；另一边，许多的中国人赞叹，。。。 今天（6月17日）是法国高考（BAC）的第一天，考试科目为“哲学”，题目分文科卷、理科卷、经济社会科卷等，考试时间4个 ...

个人分类: 在中法文化之间流连|10778 次阅读|16 个评论 热度 12

漫谈“汉字”（6）－ “緣”

热度 4 柳渝 2015-6-14 03:49

我和法国朋友Didier、Jean－François一起，开了个法语博客“Le coeur et l’esprit（ http://coeur-et-esprit.blogspot.fr ）”，对应的英语名是“heart and mind” ，缘起：“心”是中国文化的核心概念，而“mind”则是西方文化的核心概念。 如博客前言简介，此博客旨在为日常生活中的中法文化交流提供一个空间， ...

个人分类: 在中法文化之间流连|2987 次阅读|18 个评论 热度 4

本页有 1 篇博文因作者的隐私设置或未通过审核而隐藏