计算机科学中仍然存在问题的问题

17

请注意,单向函数意味着 P != NP。 - Captain Segfault
15个回答

27

我还没搞清楚“任意键”在哪里。



好吧,说正经的(为了做出有价值的贡献),如何将并行计算应用于“串行”任务的问题呢?串行计算的理论极限已经达到,而并行计算没有理论极限。然而,将并行计算应用于串行问题非常困难。例如,一个串行问题可能需要一系列计算,每个计算的结果都依赖于前一个计算的结果。如何以并行方式完成这个任务呢?

这篇文章从理论角度阐述了这些问题,并提出了投机计算作为可能的解决方案(同时指出人脑有趣的一点)。然而,这是一个非常新的领域,解决方案并不容易。


5
哈哈,回答太多了。但我想知道你们怎么会忽略这个:一个遵循W3C CSS规则集中每个CSS规则的浏览器。为什么我无法提交答案,它显示页面未找到的错误。 - pokrate
@pokrate:因为那不是计算机科学问题,你的意思应该是“CSS规范”,而且有不止一个CSS规范(所以你的回答含糊不清),但主要是因为可以想象出解决方案,所以这是一个不好的答案。我们甚至不知道是否有些计算机科学问题是可解决的。@zombat:阿姆达尔定律和古斯塔夫森定律是适用的。 - outis
你如何以并行的方式完成这个任务?如果你的架构足够并行,可以同时计算所有可能的结果(或至少几个可能的结果),然后选择与串行形式中第一个计算结果匹配的结果。但这很可能需要非常高度并行的架构才能高效地实现。 - JAB

10

找到一个共识,确定使用哪种编程语言来解决什么问题。


1
答案是“Emacs”。...什么? - zombat

8
自然语言处理确实行之有效。真不敢相信这还没有被提到过。

1
如果你能够编写一个可以比较哪个自然语言处理算法“真正有效”或者“更优秀”的算法,那将是一个好的开始! - Jared Updike

3

啊,无尽的创造性拖延可能性。我的老板不会高兴的... - Don Johe

3

图同构问题。

基本上,大多数自然发生的问题要么很容易(P),要么很可能很难(NP)。如果我没记错的话,有2或3个问题处于“中间”位置。素性测试是其中之一,但最近已经证明在P中。图同构是另一个。

图同构问题是这样一个问题:给定G1和G2,G2是否只是G1,但“重新标记”了?等价地,我们能否重新标记G2,使其与G1完全相同?

维基百科文章!一个通用的概述,以及关于其复杂度类问题的文章在这里

编辑:我真的必须记住输入所有单词。


3

对于 伸展树 的动态最优性。

将一组查询插入到二叉搜索树中。(“查找节点6。查找节点13。查找节点42”...)伸展树是静态最优的:如果你创建了一个固定的二叉搜索树并运行这些查询,它的运行速度不会比运行这些查询在伸展树上慢多少。

这有点像把苹果和橙子进行比较,因为伸展树不是静态树。未解决的问题是伸展树是否是动态最优的:它是否在修改自身的树中与之相差不超过一个常数因子?


+1 - 有趣。我以前从未听说过这些。 - zombat

3

ORM是计算机科学中的越南战争-Ted Neward。

也就是说,对于许多人来说,它并没有得到令人满意的解决。


1
或者说这是一项昂贵且基本上毫无意义的练习,没有成功的希望? - Clayton

2

虽然这可能太笼统了。我想这取决于“问题”的含义。如果图灵测试相关,我猜也是如此。 - Smandoli
当我阅读维基百科文章时,我确信这更属于“大挑战”类别。有趣的是,它在http://en.wikipedia.org/wiki/Grand_Challenge_problem中找不到。那怎么可能呢? - Smandoli
在2016年,这已经实现了。 - mauris

1

将UI元素绑定到数据库。

有许多可怜的尝试,虽然我不想这么说,但.NET可能是今天最好的。想想看:在过去的30年里,为一个有多个地址的人构建一个简单的编辑器仍然很麻烦。


4
虽然这是一个有趣的问题,但它实际上与计算机科学无关。也许与软件工程有关,但和CS没关系。 - Tal Pressman
3
同样地,如何将数据库纳入源代码控制也是一个问题。虽然这不是计算机科学领域内的问题,但它仍未得到解决。 - Unsliced

1
这里有一个有趣的问题定义。问题就是在给定资源下改进的空间(并且未被证明无法解决)。因此,按照这个新定义,在每个领域中都存在许多问题。
问题可能是将阶乘复杂度的解决方案改进为指数复杂度的解决方案(如果没有被证明不存在的话)。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接