# Questions tagged [p-vs-np]

The tag has no usage guidance.

162 questions
Filter by
Sorted by
Tagged with
3k views

### Does $\mathsf{P} \ne \mathsf{NP}$ imply that $|\mathsf{NP}| > |\mathsf{P}|$?

Is it possible that $\mathsf{P} \not = \mathsf{NP}$ and the cardinality of $\mathsf{P}$ is the same as the cardinality of $\mathsf{NP}$? Or does $\mathsf{P} \not = \mathsf{NP}$ mean that $\mathsf{P}$ ...
394 views

### Implications of polynomial time reductions

I'm reviewing for finals and have a sample problem that I think I understand, but would like someone to bless my understanding or smack me and tell me why I'm wrong. I'm presented with a problem $\Pi$...
639 views

### What would an exponential reduction from an NP-complete problem to P signify?

Taking an NP-complete problem like vertex cover if we can find a reduction which is exponential and not polynomial and the reduction we do to a problem can be solved in polynomial time, then what ...
578 views

### Proving that if $\mathrm{NTime}(n^{100}) \subseteq \mathrm{DTime}(n^{1000})$ then $\mathrm{P}=\mathrm{NP}$

I'd really like your help with proving the following. If $\mathrm{NTime}(n^{100}) \subseteq \mathrm{DTime}(n^{1000})$ then $\mathrm{P}=\mathrm{NP}$. Here, $\mathrm{NTime}(n^{100})$ is the class of ...
2k views

### How can P =? NP enhance integer factorization

If ${\sf P}$ does in fact equal ${\sf NP}$, how would this enhance our algorithms to factor integers faster. In other words, what kind of insight would this fact give us in understanding integer ...
387 views

### Are there are problems in NP that have been shown to be not NP-complete but it is still not known if they are in P or not?

I am not talking about NP-indeterminate class because those problems have to be shown to not exist either in P or NP-complete class and existence of such problems proves P!=NP. I am interested to know ...