Questions tagged [p-vs-np]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
12
votes
5answers
5k views

Flaw in my NP = CoNP Proof?

I have this very simple "proof" for NP = CoNP and I think I did something wrongly somewhere, but I cannot find what is wrong. Can someone help me out? Let A be some problem in NP, and let M be the ...
6
votes
1answer
766 views

$1+\epsilon$ approximation for inapproximable problems

I am currently confused by the following situation: 1) The metric $k$-center problem is inapproximable in polynomial time within $2-\epsilon$ unless $P=NP$. 2) The metric $k$-center problem can ...
11
votes
2answers
12k views

Is the open question NP=co-NP the same as P=NP?

I'm wondering this based on several places online that call $\sf NP=$ co-$\sf NP$ a major open problem... but I can't find any indication as to whether or not this is the same as $\sf P=NP$ problem...
3
votes
1answer
115 views

Is it necessary for NP problems to be decision problems?

Professor Tim Roughgarden from Stanford University while teaching a MOOC said that solutions to problems in the class NP must be polynomial in length. But the wikipedia article says that NP problems ...
259
votes
7answers
120k views

What is the definition of P, NP, NP-complete and NP-hard?

I'm in a course about computing and complexity, and am unable to understand what these terms mean. All I know is that NP is a subset of NP-complete, which is a subset of NP-hard, but I have no idea ...
0
votes
1answer
248 views

Recusively Enumerable or Recursive dependent on whether P=NP

If a language is defined such that $L = (0+1)^{\ast}$ if $\mathsf{P} = \mathsf{NP}$ and $\emptyset$ otherwise Then $L$ is a regular language if $\mathsf{P} = \mathsf{NP}$, otherwise it is the ...
3
votes
1answer
476 views

If NP $\neq$ Co-NP then is P $\neq$ NP

Does the proof of the widely believed result P $\neq$ NP depend on the proof of NP $\neq$ Co-NP ?
13
votes
3answers
5k views

Proving P = NP without mathematical statements / computer program

This is my first post after being a passive user for some time now. I wish to ask some questions if I may. I am not a mathematician but my question relates to the field of maths/computer science. In ...
20
votes
3answers
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}$ ...
2
votes
2answers
414 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$...
5
votes
1answer
668 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 ...
10
votes
3answers
634 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 ...
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
402 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
311 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
226 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
223 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.
99
votes
5answers
15k 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....
34
votes
4answers
22k 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 ...
29
votes
3answers
3k 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 ...

1 2 3 4