Question2: complexity of 3-SAT - CS版 - 未名存档

本页内容为未名空间相应帖子的节选和存档，一周内的贴子最多显示50字，超过一周显示500字访问原贴

CS版 - Question2: complexity of 3-SAT

相关主题
● 谁有什么solution吗？	● 请问哪里有introduction to complexity的习题解答？
● 推荐几本理论的书吧	● [合集] 谁来给CS定义一下最基本的知识结构吧？
● [转载] CS interview question	● Dijkstra SSSP@CLR的疑问 (转载)
● A question on NP-hard, maybe sound stupid	● [合集] 读计算机两年博士毕业需不需要拖到三年？
● 求教优化算法迫切等待。多谢	● 请教一个算法问题，关于点和点之间距离
● About the optimal algorithms on matching	● shortest path algorithm(dijkstra)的变形
● Transportation problem	● Question: complexity of subset sum
● 问一下primitive recursive function等于哪些其它的complexity class？	● communication complexity?

相关话题的讨论汇总
话题: complexity话题: question2话题: sat

进入CS版参与讨论

1

(共1页)

t*s 发帖数: 1504	1 x variables, y clauses complexity is exponential of min(x,y), right?
h*******e 发帖数: 225	2 it is meaningless to express in this way since y = O(x). 【在 t*s 的大作中提到】 : x variables, y clauses : complexity is exponential of min(x,y), right?

1

(共1页)

进入CS版参与讨论

相关主题
● communication complexity?	● 求教优化算法迫切等待。多谢
● 问一个算法的问题?	● About the optimal algorithms on matching
● multicast在现在网路上是不是还是理论上可行，现实中很少用？ (转载)	● Transportation problem
● 同学们，计算原理还真难啊。	● 问一下primitive recursive function等于哪些其它的complexity class？
● 谁有什么solution吗？	● 请问哪里有introduction to complexity的习题解答？
● 推荐几本理论的书吧	● [合集] 谁来给CS定义一下最基本的知识结构吧？
● [转载] CS interview question	● Dijkstra SSSP@CLR的疑问 (转载)
● A question on NP-hard, maybe sound stupid	● [合集] 读计算机两年博士毕业需不需要拖到三年？

相关话题的讨论汇总
话题: complexity话题: question2话题: sat

未名新帖统计// 7月16日

#	版面	帖数(主题数)
-	全站	4871 (796)
1	Military	3777 (569)
2	Stock	341 (51)
3	Joke	117 (17)
4	History	116 (3)
5	Automobile	100 (9)
6	USANews	55 (9)
7	Midlife	45 (1)
8	Headline	41 (41)
9	Dreamer	33 (13)
10	FleaMarket	32 (20)
11	Living	30 (7)

* 这里只显示发帖超过25的版面，努力灌水吧:-)