个人中心
文章发布
退出
作者热门文章
- iOS/Objective-C 元类和类别
- objective-c - -1001 错误，当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
27
4
要使一个问题成为 NP 完全问题，它必须属于 NP 类，并且必须有一个多项式时间算法将其简化为 NP 完全问题。
现在如果我们只有一个指数时间算法来减少会怎样。这个问题还会被称为 NP-complete 吗？还是不存在这样的问题？
编辑:另外请告诉我是否存在此类问题，如果存在，那么它属于哪个类？
最佳答案
只有其他NP问题可以在多项式时间内归约到它，才能认为是NP完全问题。这是一个有用的定义的原因是，如果我们找到一个多项式时间算法，它会自动为所有 NP 问题给出一个。如果我们允许指数时间减少，但找到了减少问题的多项式时间解决方案，那实际上不会帮助我们解决我们减少到的问题。
希望这对您有所帮助。
关于algorithm - 'reduction of problem be done in polynomial time' 是否必须是 NP 完整的？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/14789840/
27
4
0
我感到困惑...... 我在 .jsp 中编写了一个小例程。最后需要关闭ResultSet、Statement和Connection。我也在finally { }中编写了结束代码，但是当页面运行时，它
我在 Stack Overflow 上读到一些 C 函数是“过时的”或“应该避免”。你能给我一些这种功能的例子以及原因吗？ 这些功能有哪些替代方案？ 我们可以安全地使用它们 - 有什么好的做法吗？ 最
我正在构建一个应用程序，它可以拍照、显示图片，然后一旦被点击，就会在点击的任何地方返回图片的颜色。 它在崩溃之前到达了水龙头。我得到 x 必须是 < bitmap.width() 的错误 就我的理解而
我试图根据几个因素向用户提出建议: •建议只能是同一所大学的学生•建议必须至少匹配一个其他字段 我以为我有它，但问题是这个查询将返回同一所学校的所有学生，而不管其他情况: PUT /user/.per
我的应用程序必须从第三方读取 SSL 网址。我如何最好地将第三方凭证存储在我自己的数据库中，以保护第三方凭证不被泄露？兼顾绝对的安全性和实用性。对凭据进行单向哈希处理没有用，因为我必须将凭据恢复为明文
在我的 Rails API 中，我希望 Mongo 对象作为 JSON 字符串返回，Mongo UID 作为“id”属性而不是“_id”对象。 我希望我的 API 返回以下 JSON: { "
假设应用层协议(protocol)是通过UDP实现的。客户端需要超时，因此服务器需要保留与其通信的每个客户端的状态。 还假设使用了select。 实现多线程服务器总是最好的吗？我认为链接列表也会做同样
考虑一个非常短的程序，我在其中分配了一点内存。我被告知，GC 在程序分配大量内存并且分配达到限制的情况下运行。 我不知道这个限制到底是多少，但我认为它必须足够高，这样 GC 才不会频繁运行并减慢程序的
根据 Cocoa with Love当应用程序需要 WiFi(而不是蜂窝网络)时需要可达性，例如如果应用加载大量视频并且不适合在 3G 网络上使用。 我的应用程序使用互联网，无论是 WiFi 还是 3
我正在寻找更好的解决方案来解决我面临的这个问题。 如果您将鼠标悬停在缩略图上，它会淡出较大的镜头并淡入新的镜头，这很好，但是当转到目标缩略图并且您的鼠标再悬停一些时，它会更改为您的鼠标经过并拍摄的其他
启用 UAC 并使用管理帐户登录后，您将获得两个 token : 提升的 token ；这已启用 Administrators 组，具有高完整性(即强制性完整性标签 SID 为 S-1-16-1228
我想知道在 React 中创建动态选择组件的规范方法是什么。我是否必须创建一个单独的组件来根据下面的代码返回选项，以便能够通过每个条目的 props 自定义值，然后将它们包含到单独的选择组件中？ p>
我有一个启用了分页的数据网格。我根据过滤条件在数据网格中显示结果。我已经过滤了数据，现在有 2 页。当我转到第二页时。我正在再次执行搜索功能以缩小结果范围。然后我收到类似“无效的 CurrentPag
我有原始文本列，其值类似于“2012-07-26T10:33:34”和“2012-07-26T10:56:16”。在使用 Joda-Time 的 Java 中，我可以通过调用 轻松地将其转换为日期/从
您好，我被分配了一项棘手的任务。我需要让一个方形 div 到达顶部的一个点。基本上它看起来像一个正方形 div，顶部有一个宽三 Angular 形。请参阅下面的屏幕截图。顶部的深蓝色只是堆叠在白色 d
我想知道，为什么我们在 android 中使用不同的启动器图标(大小)。目前您“必须”将图标大小调整为: LDPI - 36 x 36 MDPI - 48 x 48 HDPI - 72 x 72 XH
在 SO 的几个地方，声称必须知道对象的确切类型并基于此做出决定(以 if-then-else 方式)指向一个设计缺陷，例如here . 我想知道是否总是如此。在当前的一个小型教育项目(我正在使用它来
据我了解，迭代器是一种为客户端提供接口(interface)以观察/迭代/传递自定义集合等内容的机制，而不破坏信息隐藏原则。 STL 容器有自己的迭代器，所以我们可以毫无问题地对它们使用 for (
我在 Golang 中编写了一个包装函数，用于从多个文件中渲染模板，如下所示: func RenderTemplate(w http.ResponseWriter, data interface{},
据我了解，size_type 和 difference_type 的目的不仅仅是符号——它也是为了解决例如分段架构等，它们可能具有不同的大小。 在这种情况下，如果我有一个带有随机访问迭代器的容器，那么
我是一名优秀的程序员,十分优秀！