Questions tagged [p-vs-np]
The p-vs-np tag has no usage guidance.
38
questions
333
votes
7
answers
161k
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 ...
- 4,359
106
votes
5
answers
18k
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....
- 72.8k
14
votes
5
answers
7k
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 ...
- 171
66
votes
9
answers
13k
views
What would be the real-world implications of a constructive $P=NP$ proof?
I have a high-level understanding of the $P=NP$ problem and I understand that if it were absolutely "proven" to be true with a provided solution, it would open the door for solving numerous problems ...
- 839
36
votes
3
answers
4k
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 ...
- 629
23
votes
2
answers
23k
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...
- 4,359
23
votes
3
answers
4k
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}$ ...
- 417
12
votes
1
answer
554
views
Why is this argument for $P\neq NP$ wrong?
I know its silly, but i managed to confuse myself and i need help settling this
Suppose $P=NP$, then clearly for every oracle $A$ we have $P^A=NP^A$ which contradicts the
fact that there exists some ...
- 13.5k
4
votes
1
answer
664
views
Existence of NP problems with complexity intermediate between P and NP-hard
Assuming P!=NP, there is a result that there are decision problems intermediate between P and NP-complete. That is, the class NP cannot be a union of two disjoint subsets: P and NP-complete.
I could ...
- 580
14
votes
2
answers
15k
views
How to prove P$\neq$NP?
I am aware that this seems a very stupid (or too obvious to state) question. However, I am confused at some point.
We can show that P $=$ NP if and only if we can design an algorithm that solves any ...
- 1,455
14
votes
1
answer
2k
views
Why do Shaefer's and Mahaney's Theorems not imply P = NP?
I'm sure someone has thought about this before or immediately dismissed it, but why does Schaefer's dichotomy theory along with Mahaney's theorem on sparse sets not imply P = NP ?
Here's my ...
- 1,631
12
votes
3
answers
2k
views
Why does Schaefer's theorem not prove that P=NP?
This is probably a stupid question, but I just don't understand. In another question they came up with Schaefer's dichotomy theorem. To me it looks like it proves that every CSP problem is either in P ...
- 2,511
10
votes
6
answers
6k
views
Evolving artificial neural networks for solving NP problems
I've recently read a really interesting blog entry from Google Research Blog talking about neural network. Basically they use this neural networks for solving various problems like image recognition. ...
- 377
8
votes
2
answers
1k
views
Why doesn't Godel's Second Incompleteness Theorem rule out a formalizable proof of P!=NP?
I'm sure there must be something wrong with the following reasoning because otherwise a lot of P vs. NP research would be curtailed but I cannot determine my error:
For any fixed integer $k>0$ ...
- 1,631
7
votes
6
answers
2k
views
How is it valid to use oracles in mathematical arguments?
Oracles do not exist. If one did exist, then you would replace them with a subroutine with computational requirements and you would no longer need an "Oracle". Thus, Oracles do not exist almost by ...
- 111
4
votes
1
answer
9k
views
If P = NP, why does P = NP = NP-Complete? [duplicate]
If P = NP, why does P = NP also then equal NP-Complete?
I.e. Why would it then be the case that ...
- 141
4
votes
1
answer
274
views
Provability of NP /= P?
I'm a novice to the topic of provability so bear with me...
During a discussion with a friend, the question came up whether it could be possible that proving that $NP \neq P$ (or $NP = P$) is an ...
- 41
3
votes
1
answer
2k
views
Chomsky Hierarchy and P vs NP
I have read multiple questions here that involve this kind of subject but I haven't found any definite answer. In what class do regular languages belong? (P or NP or some regular are P and other NP), ...
user102382
1
vote
2
answers
1k
views
P=NP, isn't it?
Cook and Levin showed in 1971 how deterministically in polynomial time from every non deterministic Turing machine M, that halts in polynomial number of moves/steps, and string w to create the boolean ...
user82913
1
vote
1
answer
139
views
Unpacking the notion of "hardest instances" for NP-complete problems
Suppose, for the sake of argument, that it was proved that $P \not= NP$. Then, this would imply that for every $NP$-complete problem, there is a "hardest instance" of the problem that ...
- 291
44
votes
4
answers
37k
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 ...
- 563
11
votes
1
answer
4k
views
If $\mathbf{P} = \mathbf{NP}$, then is $\mathbf{L} = \mathbf{NL}$?
If $\mathbf{P} = \mathbf{NP}$, then is $\mathbf{L} = \mathbf{NL}$? I am asking this question because, for other non-deterministic classes, it seems $\mathbf{P} = \mathbf{NP}$ always establishes that ...
- 111
11
votes
1
answer
572
views
If one shows that UNIQUE k-SAT is in P, does it imply P=NP?
Valiant & Vazirani proved SAT is reducible to UNIQUE SAT under randomized probabilistic reductions in polynomial time. Calabro et al. showed that UNIQUE k-SAT is as hard as k-SAT. Now the ...
- 190
10
votes
3
answers
1k
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 ...
- 511
7
votes
2
answers
1k
views
Polytime algorithm for SUBSET-SUM assuming P=NP
In the Wikipedia page on P vs. NP problem there is an algorithm that "solves" SUBSET-SUM in case P=NP in polynomial time. (It's idea is to find a TM that gives a certificate). But it gives "yes" in ...
- 81
6
votes
2
answers
247
views
Does Provable P equal Provable NP?
My question is a very basic one. It seems feasible to believe that $\mathsf{P = NP}$, because there is some "pathological" good algorithm for SAT, yet it is impossible to prove that the algorithm is ...
- 7,158
5
votes
0
answers
131
views
research on OR and AND compression in SAT formulas [closed]
this is a new/advanced paper on OR and AND compression of SAT formulas, a newer area of research that seems not covered in any textbooks so far.
A simple proof that AND-compression of NP-complete ...
- 11.1k
4
votes
1
answer
7k
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 ...
- 323
3
votes
1
answer
773
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 ?
- 219
2
votes
1
answer
319
views
Can you apply neural networks to design algorithms?
I’m kind of a newbie to neural networks (and CS in general) but I was wondering if there are any methods to apply them in such a way with the aim of producing algorithms that solve difficult math ...
- 21
2
votes
2
answers
256
views
Why does showing that a NP problem is not NP-complete implies P$\neq$NP?
I found in this answer that if a problem is shown to be NP but not NP-complete then P$\neq$NP. What is the argument to prove this statement?
- 36
2
votes
1
answer
990
views
Homomorphism erasing information
I would be grateful if anyone could help me with the tricky exerciese *7.52 from Sipser's Introduction to the Theory of Computation 3rd ed.
I got stuck in proving that, if P is closed under ...
- 123
1
vote
2
answers
3k
views
If an NP-complete problem is shown to have a non-polynomial lower bound, would that prove that P != NP?
I understand that the Cook-Levin theorem proved that any NP problem is reducible to an NP-complete problem, which signifies that if a polynomial-time algorithm for an NP-complete problem is found, it ...
- 13
1
vote
1
answer
3k
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, ...
- 553
1
vote
1
answer
243
views
Doubts about Baker-Gill-Solovay
How am I supposed to read the P=?NP relativization proof? I am reading the classical paper Relativization of the P=?NP problem by Baker, Gill and Solovay, in particular the proof that there exist an ...
- 21
-1
votes
2
answers
349
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?
TesterNP
-2
votes
2
answers
597
views
Does NP-hard problems have to be decision problems? (What the fact please) (contradicting answers)
Let me explain my trouble by another example.
The wiki page says that
Lattice problems are an example of NP-hard problems
However, by clicking NP-hard, i find this definition
A decision problem H ...
- 9
-2
votes
1
answer
662
views
If X is polynomial reduction to Y and Y is in NP, then X is in NP? [duplicate]
If X is polynomial reduction to Y and Y is in NP, then X is in NP?
Is this true, false or "we don't know"? Why?
- 31