R \ P中的问题（寻找一个例子）

我正在研究可计算性理论，并且我正在寻找一个显然可以解决的问题，但不是在多项式时间内。R P中的问题（寻找一个例子）

我试过的例子所有种类的思维，但目前还不清楚为什么他们不能在多项式时间内解决..

2012-02-11 Belgi

http://en.wikipedia.org/wiki/Computational_complexity_theory#Problems_in_NP_not_known_to_be_in_P_or_NP-complete – 2012-02-11 09:14:25

如果P = NP它不是例子... – Belgi 2012-02-11 09:19:25

没有人知道P = NP！ – 2012-02-11 09:21:08

2012-02-11 09:13:49

谢谢，我正在寻找更简单的东西，显然不是P – Belgi 2012-02-11 09:20:26

这很简单。你需要检查所有可能的路径。添加节点会以指数方式增加搜索空间。不像最短路径没有捷径。用最短的路径可以修剪搜索空间。 – 2012-02-11 09:23:37

回答