﻿ oipapio

### p vs np - Why do computer scientists on the whole work under the assumption that P ≠ NP?

Coming from a math background, it seems interesting to me that on the whole computer scientists tend to work under the assumption that \$P \neq NP\$. While there is no proof either way, generally, unless something can be specifically unproven in both math and science it is taken with a fair amount of strength. I feel that in the years and years people have spent trying to disprove \$P = NP\$, the fact that no proof has been discovered yet would at least lead some computer scientists to work within the parameters of viewing \$P = NP\$ as possibly true...Read more

### p vs np - Barriers to show \$P=NP\$

We all know showing \$P\ne NP\$ has barriers. We all have studied these barriers because we believe \$P\ne NP\$.However assume \$P=NP\$ and there are wise people who believe that possibility exists. If this is indeed the case then the very fact that we have not seen any good algorithms indicates there might be barriers in this alternate universe as well. Provability of \$P\ne NP\$ is barrier ridden and we do not know for sure \$P\ne NP\$ is the truth. We do not know for sure \$P= NP\$ is the truth either and so is provability of \$P=NP\$ also barrier ridden?...Read more

### p vs np - Effective Procedures and P vs NP Problem

If, suppose, P doesn't equal NP. Implication of this statement is that there is no effective procedure to solve a hard problem; however there exists an acceptable solution S. I have following two explicit queries:If an effective procedure cannot be given which yields a solution, in what sense is the S actually a solution? Does this defy the formal definition of solution? I am assuming that an effective procedure is equivalent to a proof. If there is no effective procedure to arrive at an accepted solution, this implies that solution is not a s...Read more

### p vs np - Can we detect perfect matchings in P? in NP? in coNP?

This question concerns the classes P and N P . If you are familiar with them, you may skip the definitions and go directly to the question. Let L be a set. We say that L is in P if there is some algorithm which given input x decides if x is in L or not in time bounded by a polynomial in the length of x. For example, the set of all connected graphs is in P , because there is an algorithm which, given a graph graph, can decide if it is connected or not in time roughly proportional to the number of edges of the graph.The class NP is a superset of ...Read more

### p vs np - Can one prove the discovery of a P versus NP solution without actually revealing it?

Suppose a person has proved that P≠NP. He wants to let the world know that he has solved the P versus NP problem but does not want to reveal that he has proved P≠NP as opposed to P=NP. Is there any purely theoretical way to do so?Also any practical evidence he can show to back his claim? (I'm not sure it this part is on-topic)...Read more