Math 版 (精华区)

发信人: builder (打工仔), 信区: Math
标  题: [合集]有没有把逻辑表达式转化成析取或合取范式的...
发信站: 哈工大紫丁香 (2001年09月13日08:53:22 星期四), 站内信件


────────────────────────────────────────
 ssos (存在与虚无)                    于 2001年06月19日16:58:51 星期二 说道:

是NP问题
【 在 melancholy (前寒武纪) 的大作中提到: 】
: 顺便问一下，有没有关于合取与析取范式之间相互转化的
: 计算复杂性的研究？
: 3x！

────────────────────────────────────────
 utah (尤他去吧)                      于 2001年06月19日17:01:18 星期二 说道:

有么〉
【 在 ssos (存在与虚无) 的大作中提到: 】
: 是NP问题
: 【 在 melancholy (前寒武纪) 的大作中提到: 】
: : 顺便问一下，有没有关于合取与析取范式之间相互转化的
: : 计算复杂性的研究？
: : 3x！

────────────────────────────────────────
 melancholy (前寒武纪)                于 2001年06月19日20:14:14 星期二 说道:

就是说 No Problem么？
^_^.
【 在 ssos (存在与虚无) 的大作中提到: 】
: 是NP问题
: 【 在 melancholy (前寒武纪) 的大作中提到: 】
: : 顺便问一下，有没有关于合取与析取范式之间相互转化的
: : 计算复杂性的研究？
: : 3x！

────────────────────────────────────────
 ssos (存在与虚无)                    于 2001年06月19日20:32:16 星期二 说道:

是问题的复杂性在多项式时间内解决不了
【 在 melancholy (前寒武纪) 的大作中提到: 】
: 就是说 No Problem么？
: ^_^.
: 【 在 ssos (存在与虚无) 的大作中提到: 】
: : 是NP问题

────────────────────────────────────────
 melancholy (前寒武纪)                于 2001年06月20日18:55:01 星期三 说道:

哈哈，不好意思，开个玩笑而已。
其实np问题3系谁人不知�
只要一个问题被归为np问题，就像被
判了死刑一样。如果觉得自己没有拿
图灵奖兼菲而兹奖的实例基本上可以考虑
全身而退了。只是有一次同学求我办点事，
我回答他说NP，他楞了一下，估计是想
这么点事竟然是NP难的？为解除他的疑虑，
我立刻解释道：是No Problem的意思。
【 在 ssos (存在与虚无) 的大作中提到: 】
: 是问题的复杂性在多项式时间内解决不了
: 【 在 melancholy (前寒武纪) 的大作中提到: 】
: : 就是说 No Problem么？
: : ^_^.

────────────────────────────────────────
 ssos (存在与虚无)                    于 2001年06月20日19:28:21 星期三 说道:

我正在调这个程序
【 在 melancholy (前寒武纪) 的大作中提到: 】
: 哈哈，不好意思，开个玩笑而已。
: 其实np问题3系谁人不知�
: 只要一个问题被归为np问题，就像被
: 判了死刑一样。如果觉得自己没有拿
: 图灵奖兼菲而兹奖的实例基本上可以考虑
: 全身而退了。只是有一次同学求我办点事，
: 我回答他说NP，他楞了一下，估计是想
: 这么点事竟然是NP难的？为解除他的疑虑，
: 我立刻解释道：是No Problem的意思。
: 【 在 ssos (存在与虚无) 的大作中提到: 】

────────────────────────────────────────
 melancholy (前寒武纪)                于 2001年06月21日09:53:49 星期四 说道:

顺便问一下,范式转化问题复杂性分析时,
问题的复杂性是怎样描述的?我想这对于我
考虑的问题是重要的.或许对于我的问题
描述并不是NP的.
【 在 ssos (存在与虚无) 的大作中提到: 】
: 我正在调这个程序
: 【 在 melancholy (前寒武纪) 的大作中提到: 】
: : 哈哈，不好意思，开个玩笑而已。
: : 其实np问题3系谁人不知�
: : 只要一个问题被归为np问题，就像被
: : 判了死刑一样。如果觉得自己没有拿
: : 图灵奖兼菲而兹奖的实例基本上可以考虑
: : 全身而退了。只是有一次同学求我办点事，
: : 我回答他说NP，他楞了一下，估计是想
: : 这么点事竟然是NP难的？为解除他的疑虑，
: : 我立刻解释道：是No Problem的意思。

────────────────────────────────────────
 ssos (存在与虚无)                    于 2001年06月23日08:24:17 星期六 说道:

程序编出来了
好像不是NP的
下面是我程序的形式化描述,你看看看有什么问题没有:
将范式写成树的形式,对树进行后根遍历,对于每一个结点
如果结点是叶结点,返回
如果结点是合取范式
对于每一个儿子结点,如果是叶结点或者析取范式,不变,如果儿子结点是合取范式,则将
这个结点的儿子结点连接到这个结点所有的儿子结点之后,将这个结点释放.
 如果结点是析取范式根据它的两个儿子结点left,right的情况加以判断(从原来查询
树直接转换过来的查询条件树,只有两个儿子结点)
如果left和right都是合取范式,则将两个结点的每一对儿子结点通过连接起来构成一个
析取范式.
如果其中之一为合取范式另一个为析取范式则将合取范式的每一个儿子结点和析取范式
的儿子结点连接成析取范式.将所有的范式连接成合取范式
如果其中之一为合取范式,另一个为叶结点,则将叶结点和合取范式中的每一个儿子序列
结点用查询连接成析取范式. 将所有的范式连接成合取范式.
如果一个儿子结点是叶结点,另一个结点是析取范式,则将叶结点接到析取范式的叶结点
之后.
如果两个结点都是析取范式,则将两个结点的儿子结点连接在一起成为一个析取范式.
【 在 melancholy (前寒武纪) 的大作中提到: 】
: 顺便问一下,范式转化问题复杂性分析时,
: 问题的复杂性是怎样描述的?我想这对于我
: 考虑的问题是重要的.或许对于我的问题
: 描述并不是NP的.
: 【 在 ssos (存在与虚无) 的大作中提到: 】
: : 我正在调这个程序

────────────────────────────────────────
 melancholy (前寒武纪)                于 2001年06月23日10:14:32 星期六 说道:

不好意思的说，看不太懂。
我对这个算法不是很熟。
不过用几个例子验证一下
就知道对不对了。
【 在 ssos (存在与虚无) 的大作中提到: 】
: 程序编出来了
: 好像不是NP的
: 下面是我程序的形式化描述,你看看看有什么问题没有:
: 将范式写成树的形式,对树进行后根遍历,对于每一个结点
: 如果结点是叶结点,返回
: 如果结点是合取范式
: 对于每一个儿子结点,如果是叶结点或者析取范式,不变,如果儿子结点是合取范式,则将
: 这个结点的儿子结点连接到这个结点所有的儿子结点之后,将这个结点释放.
:  如果结点是析取范式根据它的两个儿子结点left,right的情况加以判断(从原来查询
: 树直接转换过来的查询条件树,只有两个儿子结点)
: 如果left和right都是合取范式,则将两个结点的每一对儿子结点通过连接起来构成一个

────────────────────────────────────────
 ssos (存在与虚无)                    于 2001年06月23日13:17:38 星期六 说道:

说实话
简单的例子肯定对
例子太复杂了,连人都不知道对不对了
【 在 melancholy (前寒武纪) 的大作中提到: 】
: 不好意思的说，看不太懂。
: 我对这个算法不是很熟。
: 不过用几个例子验证一下
: 就知道对不对了。
: 【 在 ssos (存在与虚无) 的大作中提到: 】
: : 程序编出来了
: : 好像不是NP的
: : 下面是我程序的形式化描述,你看看看有什么问题没有:
: : 将范式写成树的形式,对树进行后根遍历,对于每一个结点
: : 如果结点是叶结点,返回

────────────────────────────────────────
 ssos (存在与虚无)                    于 2001年06月23日13:18:04 星期六 说道:

不过理论上是对的
【 在 ssos (存在与虚无) 的大作中提到: 】
: 说实话
: 简单的例子肯定对
: 例子太复杂了,连人都不知道对不对了
: 【 在 melancholy (前寒武纪) 的大作中提到: 】
: : 不好意思的说，看不太懂。
: : 我对这个算法不是很熟。
: : 不过用几个例子验证一下
: : 就知道对不对了。

────────────────────────────────────────
 melancholy (庆祝！终于可以用ieee了)  于 2001年06月29日17:08:00 星期五 说道:

可以把你的程序给我一份么？
【 在 melancholy (前寒武纪) 的大作中提到: 】
: 不好意思的说，看不太懂。
: 我对这个算法不是很熟。
: 不过用几个例子验证一下
: 就知道对不对了。
: 【 在 ssos (存在与虚无) 的大作中提到: 】
: : 程序编出来了
: : 好像不是NP的
: : 下面是我程序的形式化描述,你看看看有什么问题没有:
: : 将范式写成树的形式,对树进行后根遍历,对于每一个结点
: : 如果结点是叶结点,返回

────────────────────────────────────────