The p-vs-np tag has no wiki summary.
0
votes
1answer
71 views
Proving that if coNP $\neq$ NP then P $\neq$ NP
I am new in complexity theory and this question is a part of a homework that I have and I am stuck on it.
Let ${\sf coNP}$ be the class of languages $\{\overline{L}: L \in {\sf NP} \}$.
Show ...
2
votes
1answer
54 views
Reduction from Vertex Cover to an Independent Set problem
Assume there exists some algorithm that solves vertex cover problem in time polynomial in terms of $n$ and exponential for $k$ with the run time that looks like this $O(k^2 55^k n^3)$. Can we claim ...
1
vote
1answer
60 views
How to prove polynomial time equivalence?
Define the problem $W$:
Input: A multi-set of numbers $S$, and a number $t$.
Question: What is the smallest subset $s \subseteq S$ so that $\sum_{k \in s} k = t$, if there is one? (If not, ...
0
votes
0answers
160 views
Proof that P != NP (proof-check) [closed]
A proof that P != NP.
Warning: This proof uses descriptive complexity. I would post it on cstheory.stackexchange.com , but they don't want P vs. NP proofs.
The argument that P != NP is ...
2
votes
3answers
389 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 ...
5
votes
1answer
103 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 ...
2
votes
2answers
101 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...
...
2
votes
1answer
66 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 ...
23
votes
3answers
760 views
In basic terms, 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 ...
1
vote
1answer
108 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
172 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 ?
7
votes
3answers
770 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 ...
4
votes
2answers
288 views
Does P != NP imply that | NP | > | P |?
Is it possible that P != NP and the cardinality of P is the same as the cardinality of NP? Or does P != NP mean that P and NP must have different cardinalities?
2
votes
2answers
63 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 ...
3
votes
1answer
155 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 ...
8
votes
3answers
251 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 ...
7
votes
2answers
217 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 ...
-2
votes
2answers
169 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?
5
votes
1answer
79 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 ...
7
votes
2answers
180 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.
28
votes
5answers
5k 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 ...
11
votes
4answers
1k 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 ...
