Questions tagged [p-vs-np]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
14
votes
2answers
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 ...
4
votes
1answer
379 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 ...
-1
votes
2answers
307 views

If the “is P equals to NP?” is a NP-COMPLETE, what does it tell us?. Some conclusions?

If there is someone can prove that the problem "is P equals to NP?" is a NP-COMPLETE problem, what we can conclude from this?
8
votes
1answer
225 views

How to show that the set of machines which accept languages in $\mathrm{NP}\smallsetminus\mathrm P$, is decidable only if $\mathrm P=\mathrm{NP}$?

I'd like your help with proving that the language $$L=\{\langle M \rangle \mathrel| L(M) \in \mathrm{NP}\smallsetminus \mathrm{P} \}$$ is decidable iff $\mathrm{P}=\mathrm{NP}$. If $\mathrm{P}=\...
8
votes
2answers
220 views

Can exactly one of NP and co-NP be equal to P?

Maybe I am missing something obvious, but can it be that P = co-NP $\subsetneq$ NP or vice versa? My feeling is that there must be some theorem that rules out this possibility.
96
votes
5answers
14k views

How not to solve P=NP?

There are lots of attempts at proving either $\mathsf{P} = \mathsf{NP} $ or $\mathsf{P} \neq \mathsf{NP}$, and naturally many people think about the question, having ideas for proving either direction....
31
votes
4answers
19k views

Are there NP problems, not in P and not NP Complete?

Are there any known problems in $\mathsf{NP}$ (and not in $\mathsf{P}$) that aren't $\mathsf{NP}$ Complete? My understanding is that there are no currently known problems where this is the case, but ...
28
votes
3answers
2k views

Why is Relativization a barrier?

When I was explaining the Baker-Gill-Solovay proof that there exists an oracle with which we can have, $\mathsf{P} = \mathsf{NP}$, and an oracle with which we can have $\mathsf{P} \neq \mathsf{NP}$ to ...