是否存在某种方法能够证明某个np问题能转换为p问题
我一点一点慢慢答，先留个几个要点。如果我对问题的理解有偏差，麻烦题主在评论里告知。1. 需要区别〝非确定性算法〞和 NTM NTM是同时计算出所有可能出现的结果，注意，是同时。所以只要有一条计算路径可以在多项式时间内跑完，就可以说这个问题属于NP。
====分割线内的这段可以不看……===========================
而〝非确定性算法〞可能不是并行的，比如ppt算法 (probabilistic polynomial time algorithm)，这类算法，如果你把它想象成自动机，则在运行时，每一跳会有一个随机选项。但ppt单次运行最后形成的计算路径是唯一的。这样，就没有了“同时计算出”这个性质。对于ppt最后计算出正确结果的总运行时间复杂度能求出一个期望值，而这个期望值可能并非是多项式的。但这个复杂度不代表问题不属于NP。
===============================================================
2. NP 不等于NP- Complete (NP完全)不是所有的NP问题都难。因为
.
比如，求无负环的图中两点最短路径的问题，或者验证一个字符串是否是回文的问题，都属于P，因此也属于NP，但都不是NP-Complete。
3.NP是否等于P还是个开放问题。所有的P问题都是NP问题，这个结论从两者的定义出发即可得。但反过来，即NP问题是否都是P问题，目前为止无法断言。在这个前提下，除了直接从定义出发，只能从证明特定的问题之间的等价关系开始，找寻这个问题的性质。比如SAT是个NP-complete问题，而clique问题和它等价，所以clique也是 NP-complete。要证明某个问题是否是p也类似，找到一个和它等价的、已知的p问题( 或者找到一个直接解决它的多项式复杂度算法。)
4。目前为止， NP-complete仅仅是一个复杂度假设，一个便于研究问题性质的概念。因为就如你所说，或许仅仅是因为我们都还不够聪明，所以找不到高效的算法。
============2014年12月13日更新===========================
以下区别一下NP-hard 和 NP-Complete
1. 若任何一个NP问题都能够在多项式时间内规约到问题A，则称A为NP-hard问题。
2. 若A本身属于NP，且满足1，则称A为NP-complete。
【是否存在某种方法能够证明某个np问题能转换为p问题】 区别在于，可能存在本身不属于NP，但是是NP-hard的问题。这类问题并非NP-Complete。
■网友
理论上就不行。因为只有两种情况 ：１. 这个问题只是NP，那么只是证明了这个问题是NP的这个论点是错误的。那么这个问题就被重新归类为P问题。２. 这个问题是NP-complete， 那么就证明了NP=P。PS：如果题主找到的是第二种，那五百万美金分我个十分之一怎么样！！^。^
推荐阅读
- 广东警方曝光38款存在超范围收集用户信息违规行为App
- 傻子当国有银行行长都能赚钱这句话是否是对的
- 网通社|喜欢蔚来的越来越多了 连续四个月交付创新高 你是否愿意放弃特斯拉选择它？
- 豆瓣为啥受到同志社群的欢迎
- |PHEV车款没比较环保，新能源是否存在谎言呢？
- 运营商收取的流量费用价格是否合理
- 基因是主动表达还是受某种场的影响被动表达，又或两者都有有没有隔绝所有电磁场来研究基因表达的实验
- 游戏公司一般咋识别游戏脚本
- 知乎上关于人生经验的介绍是否可能对青少年造成潜在危害
- 是否该停止密码掩饰了