blocks|key|1549949|text|你可以说我悲观，但事情会是这样的：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1549950|..。|1549951|∴，P≠NP|1549952|QED|1549953|entityMap^0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|J|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|K|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|L|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|M|8|@]|9|@]|A|$]]|$1|H|3|-4|5|6|7|N|8|@]|9|@]|A|$]]]|I|$]]

Call me pessimistic, but it will be like this: 

...

∴, P ≠ NP

QED

blocks|key|1334555|text|它可以采取证明假设P≠NP导致矛盾的形式。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1334556|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

It could take the form of demonstrating that assuming P &ne; NP leads to a contradiction.

blocks|key|1550053|text|它可能不会以一种直接的方式连接到P和NP+...现在许多定理都是基于P!=NP的，所以证明一个假设的事实是不正确的将会有很大的不同。即使证明了TS的常数比率近似，也应该足够IIRC。我认为，NPI+(GI)和其他集合的存在也是基于P!=NP的，所以使它们中的任何一个等于P或NP都可能完全改变这种情况。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1550054|现在一切都发生在一个非常抽象的层次上。如果有人证明了关于P=/!=NP的任何东西，它就不需要提到这些集合中的任何一个，甚至不需要提到特定的问题。|1550055|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|F|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|G|8|@]|9|@]|A|$]]|$1|D|3|-4|5|6|7|H|8|@]|9|@]|A|$]]]|E|$]]

It might not be connected to P and NP in a straightforward way... Many theorems now are based on P!=NP, so proving one assumed fact to be untrue would make a big difference. Even proving something like constant ratio approximation for TS should be enough IIRC. I think, existence of NPI (GI) and other sets is also based on P!=NP, so making any of them equal to P or NP might change the situation completely.

IMHO everything happens now on a very abstract level. If someone proves anything about P=/!=NP, it doesn't have to mention any of those sets or even a specific problem.

blocks|key|1334655|text|它的形式可能是从NP问题简化为P问题。请参阅reductions上的维基百科页面。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1334656|或|1334657|就像Vinay+Deolalikar提出的这个proof。|1334658|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Reduction_(complexity))|1|https://stackoverflow.com/questions/3436978/explain-the-proof-by-vinay-deolalikar-that-p-np^0|M|A|0|0|0|N|5|1|0^^$0|@$1|2|3|4|5|6|7|R|8|@]|9|@$A|S|B|T|1|U]]|C|$]]|$1|D|3|E|5|6|7|V|8|@]|9|@]|C|$]]|$1|F|3|G|5|6|7|W|8|@]|9|@$A|X|B|Y|1|Z]]|C|$]]|$1|H|3|-4|5|6|7|10|8|@]|9|@]|C|$]]]|I|$J|$5|K|L|M|C|$N|O]]|P|$5|K|L|M|C|$N|Q]]]]

Probably it would be in the form of a reduction from an NP problem to a P problem. See the Wikipedia page on <a href="http://en.wikipedia.org/wiki/Reduction_(complexity)" rel="nofollow noreferrer">reductions</a>.

OR

Like this <a href="https://stackoverflow.com/questions/3436978/explain-the-proof-by-vinay-deolalikar-that-p-np">proof</a> proposed by Vinay Deolalikar.

blocks|key|1334714|text|设N等于乘法恒等式。则NP+=+P.+QED。;-)|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1334715|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

Set N equal to the multiplicative identity. Then NP = P. QED. ;-)

blocks|key|1334864|text|最直接的方法是证明问题在NP-完全类中存在多项式时间解。这些都是NP中的问题，可以归结为一个已知的np问题。这意味着你可以给出一个更快的算法来证明original+problem+posed+by+Stephen+Cook或其他许多已经被证明是NP完全的算法。有关更多有趣的问题，请参阅Richard+Karp的seminal+paper和this+book。已经证明，如果你解决了其中的一个问题，整个复杂类就会崩溃。编辑:我必须补充说，我正在与我的朋友交谈，他正在研究量子计算。虽然我不知道这是什么意思，但他说某个证据/实验？在量子世界中，可以使整个复杂类，我的意思是，整个事情，没有意义。如果这里有人知道更多关于这方面的信息，请回复。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1334865|在没有给出正式算法的情况下，也有许多人试图解决这个问题。你可以试着数一数这一组。这是Robert/Seymore证明。人们还试图使用经过试验和测试的对角化证明来解决它(也用于表明存在永远不能解决的问题)。Razborov还表明，如果存在某些单向函数，则任何证明都无法给出解决方案。这意味着需要新的技术来解决这个问题。|1334866|从最初的论文发表到现在已经38年了，仍然没有证据的迹象。不仅如此，在复杂性类的概念出现之前，数学家们提出的许多问题都被证明是NP。因此，许多数学家和计算机科学家认为，其中一些问题是如此基本，以至于可能需要一种新的数学来解决问题。你必须记住，人类提供的最好的头脑已经解决了这个问题，但没有取得任何成功。我认为至少在几十年后才会有人解开这个谜团。但是，即使存在多项式时间解决方案，常数或指数也可能非常大，因此在我们的问题中将是无用的。|1334867|有一个很好的调查可以回答你的大多数问题：http://www.scottaaronson.com/papers/pnp.pdf。|1334868|entityMap|0|LINK|mutability|MUTABLE|url|http://portal.acm.org/citation.cfm?coll=GUIDE&dl=GUIDE&id=805047|1|http://en.wikipedia.org/wiki/Karp%2527s_21_NP-complete_problems|2|https://rads.stackoverflow.com/amzn/click/com/0716710455|3|http://www.scottaaronson.com/papers/pnp.pdf^0|21|12|0|4C|D|1|4Q|9|2|0|0|0|K|17|3|0^^$0|@$1|2|3|4|5|6|7|X|8|@]|9|@$A|Y|B|Z|1|10]|$A|11|B|12|1|13]|$A|14|B|15|1|16]]|C|$]]|$1|D|3|E|5|6|7|17|8|@]|9|@]|C|$]]|$1|F|3|G|5|6|7|18|8|@]|9|@]|C|$]]|$1|H|3|I|5|6|7|19|8|@]|9|@$A|1A|B|1B|1|1C]]|C|$]]|$1|J|3|-4|5|6|7|1D|8|@]|9|@]|C|$]]]|K|$L|$5|M|N|O|C|$P|Q]]|R|$5|M|N|O|C|$P|S]]|T|$5|M|N|O|C|$P|U]]|V|$5|M|N|O|C|$P|W]]]]

The most straightforward way is to prove that there is a polynomial time solution to the problems in the class NP-complete. These are problems that are in NP and are reducable to one of the known np problem. That means you could give a faster algorithm to prove the <a href="http://portal.acm.org/citation.cfm?coll=GUIDE&amp;dl=GUIDE&amp;id=805047" rel="nofollow noreferrer">original problem posed by Stephen Cook</a> or many others which have also been shown to be NP-Complete. See Richard Karp's <a href="http://en.wikipedia.org/wiki/Karp%27s_21_NP-complete_problems" rel="nofollow noreferrer">seminal paper</a> and <a href="https://rads.stackoverflow.com/amzn/click/com/0716710455" rel="nofollow noreferrer" rel="nofollow noreferrer">this book</a> for more interesting problems. It has been shown that if you solve one of these problems the entire complexity class collapses. edit: I have to add that i was talking to my friend who is studying quantum computation. Although I had no clue what it means, he said that a certain proof/experiment? in the quantum world could make the entire complexity class, i mean the whole thing, moot. If anyone here knows more about this, please reply.

There have also been numerous attempts to the problem without giving a formal algorithm. You could try to count the set. Theres the Robert/Seymore proof. People have also tried to solve it using the tried and tested diagonlization proof(also used to show that there are problems that you can never solve). Razborov also showed that if there are certain one-way functions then any proof cannot give a resolution. That means that new techniques will be required in order to solve this question.

Its been 38 years since the original paper has been published and there still is no sign of a proof. Not only that but lot of problems that mathematicians had been posing before the notion of complexity classes came in has been shown to be NP. Therefor many mathematicians and computer scientists believe that some of the problems are so fundamental that a new kind of maths may be needed to solve the problem. You have to keep in mind that the best minds human race has to offer have tackled this problem without any success. I think it should be at least decades before somebody cracks the puzzle. But even if there is a polynomial time solution the constants or the exponent could be so large that it would be useless in our problems.

There is an excellent survey available which should answer most of your questions: <a href="http://www.scottaaronson.com/papers/pnp.pdf" rel="nofollow noreferrer">http://www.scottaaronson.com/papers/pnp.pdf</a>.

blocks|key|1334986|text|它很可能看起来几乎和these一模一样。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1334987|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Mathematical_proof#Methods_of_proof^0|A|5|0|0^^$0|@$1|2|3|4|5|6|7|L|8|@]|9|@$A|M|B|N|1|O]]|C|$]]|$1|D|3|-4|5|6|7|P|8|@]|9|@]|C|$]]]|E|$F|$5|G|H|I|C|$J|K]]]]

It would likely look almost precisely like one of <a href="http://en.wikipedia.org/wiki/Mathematical_proof#Methods_of_proof" rel="nofollow noreferrer">these</a>

blocks|key|1549930|text|问得好；它可以采用任何一种形式。显然，特定的算法会更有帮助，是的，但无法确定理论上的P=NP证明是否会以这种方式出现。鉴于NP-complete问题的性质以及它们的普遍程度，似乎投入了更多的精力来解决这些问题，而不是投入更多的精力来解决方程的理论推理方面，但这只是假设。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1549931|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

Good question; it could take either form. Obviously, the specific algorithm would be more helpful, yes, but there's no determining that that would be the way that a theoretical P=NP proof would occur. Given that the nature of NP-complete problems and how common they are, it would seem that more effort has been put into solving those problems than has been put into solving the theoretical reasoning side of the equation, but that's just supposition.

blocks|key|1550208|text|在某种程度上，这样的证明所需要的形式取决于你的哲学观点(=你认为是正确的公理)-例如，作为一个contructivist|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1550209|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Constructivism_(mathematics%2529)%2520you%2520would%2520demand%2520the%2520construction%2520of%2520an%2520actual%2520algorithm%2520that%2520requires%2520polynomial%2520time%2520to%2520solve%2520an%2520NP-complete%2520problem.%2520This%2520could%2520be%2520done%2520by%2520using%2520reduction,%2520but%2520not%2520with%2520an%2520indirect%2520proof.%2520Anyhow,%2520it%2520really%2520seems%2520to%2520be%2520very%2520unlikely%2520:^0|1B|D|0|0^^$0|@$1|2|3|4|5|6|7|L|8|@]|9|@$A|M|B|N|1|O]]|C|$]]|$1|D|3|-4|5|6|7|P|8|@]|9|@]|C|$]]]|E|$F|$5|G|H|I|C|$J|K]]]]

To some extent, the form such a proof needs to have depends on your philosophical point of view (= the axioms you deem to be true) - e.g., as a <a href="http://en.wikipedia.org/wiki/Constructivism_(mathematics)" rel="nofollow noreferrer">contructivist</a> you would demand the construction of an actual algorithm that requires polynomial time to solve an NP-complete problem. This could be done by using reduction, but not with an indirect proof. Anyhow, it really seems to be very unlikely :)

blocks|key|1550405|text|证明将推导出一个矛盾的假设，即NP的至少一个元素(问题)不也是P的元素。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1550406|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

The proof would deduce a contradiction from to the assumption that at least one element (problem) of NP isn't also an element of P.

blocks|key|1550479|text|An+interesting+read+that+is+somewhat+related+to+this|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1550480|entityMap|0|LINK|mutability|MUTABLE|url|http://rjlipton.wordpress.com/2009/08/20/what-will-happen-when-pnp-is-proved/^0|0|1G|0|0^^$0|@$1|2|3|4|5|6|7|L|8|@]|9|@$A|M|B|N|1|O]]|C|$]]|$1|D|3|-4|5|6|7|P|8|@]|9|@]|C|$]]]|E|$F|$5|G|H|I|C|$J|K]]]]

<a href="http://rjlipton.wordpress.com/2009/08/20/what-will-happen-when-pnp-is-proved/" rel="nofollow noreferrer">An interesting read that is somewhat related to this</a>

Would it be an polynomial time algorithm to a specific NP-complete problem, or just abstract reasonings that demonstrate solutions to NP-complete problems exist?

It seems that the a specific algoithm is much more helpful. With it, all we'll have to do to polynomially solve an NP problem is to convert it into the specific NP-complete problem for which the proof has a solution, and we are done.

What would a P=NP proof be like, hypothetically?

对于特定的NP-完全问题，它将是一个多项式时间算法，还是仅仅是证明存在NP-完全问题的解决方案的抽象推理？看起来，特定的算法更有帮助。有了它，我们要做的就是将一个NP问题转化为证明有解的特定NP-完全问题，然后我们就完成了。

问假设一个P=NP证明是什么样子的？
EN

回答 11

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问假设一个P=NP证明是什么样子的？EN

回答 11

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问假设一个P=NP证明是什么样子的？
EN