我在大学里有一门名为算法分析的课程,我们目前正在研究不同的复杂性类别 - P,NP,NP-hard等.
我们已经讨论过NP完全问题作为NP与NP之间的交集,以及NP中包含的P问题.我们还讨论了一些例子,主要是NP完全问题(k-coloring,k-clique,SAT).
大多数时候,我们通过以下方式证明问题是NP完全的:
一个.找到一个不确定的算法来解决它(使用选择,成功,失败);
湾 减少已知的NP完全问题.
问题是这些问题,当在确定性机器上运行时(顺序而不是在遇到选择时同时分支)具有指数时间解决方案.
我的问题是 - 我从未遇到过在指数时间内既不能在多项式时间内解决的问题; 多项式时间问题在P中,指数时间问题通常在NP完全中.
这里有一个有用的维恩图:http: //en.wikipedia.org/wiki/Np_complete
我想知道一个问题的例子既不是在NP中,也不是在NP中.
另外,本质上是指数问题,比如生成NP-complete集的幂集？或者该名称仅适用于仅使用指数时间算法的问题,因为没有其他明显的方法可以解决它？
好的,所以我给了Rosh Oxymoron的答案,因为他实际列出了一些疑似在P和NPC之间的问题的例子.谢谢你的帮助,我实际上注意到我把这个问题放错了地方.还有:https: //cstheory.stackexchange.com/
在那里我发现了以下非常有用的回答我的问题: https://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc 这是专门约我问及: https://开头cstheory .stackexchange.com/questions/52/hierarchyies-in-np-under-the-assumption-that-p-np ,如果与初始问题不完全相关,通常很有趣.
非常感谢,
担
theory complexity-theory computer-science computation-theory
这是我的问题:我使用Emacs并获得大量无用的缓冲区,如*Messages*或*Completions*.
我想绑定\ Cy来关闭所有以*开头的缓冲区,除了*shell*(和*shell*<k>)缓冲区.
为此,我想在我的.emacs文件中添加一些Emacs-Lisp:
(defun string-prefix s1 s2
(if (> (string-length s1) (string-length s2)) nil
(string=? s1 (substring s2 0 (string-length s1))) ))
(defun curry2
(lambda (f)
(lambda (x)
(lambda (y)
(f x y) ))))
(defun filter
(lambda (f l)
(if (null? l) '()
(let ((rest (cdr l)))
(if (f (car l)) (cons (car l) rest)
rest) ))))
(defun kill-useless (arg)
(interactive "p")
(map 'kill-buffer
(filter
(not ((curry2 string-prefix) "*shell*"))
(list-buffers)
) ))
(global-set-key "\C-y" 'kill-useless)
我已经测试string-prefix并curry2 …
我首先需要提一下,我对Scheme很新,因此,下面的问题可能没有多大意义.
在学校,我们已经定义了代数数据类型,它们通常具有一个无效的构造函数和一些内部/外部的构造函数.
在这种特殊情况下,我感兴趣的是一个BTree二叉树类型(也许平衡,在未来的迭代),我想类似这样是哈斯克尔如何对待构造函数.我曾经看到过如何实现树方案,这里例如,但这不是我想要的.
我不想只是围绕列表做一个包装器.我只想写下这样的东西:
nil: -> BTree
node: BTree x T x BTree -> BTree
然后让它知道我的意思:
flattenTree: BTree -> List
然后,我将定义它被(假设left,right,key被定义):
(define flattenTree
(lambda (t)
(node (flattenTree (left t))
(key t)
(flattenTree (right t)))))
另外,我欢迎有关正确缩进我的计划代码的建议......(并且请加以修改)