Questions tagged [p-vs-np]
The p-vs-np tag has no usage guidance.
281
questions
0
votes
1
answer
41
views
P vs. NP problem and understanding "worst case complexity"
Suppose that $P \not= NP$. Then my understanding is not all instances of NP-complete problems can be solved in polynomial time. That is for every NP-complete problem, there are a colleciton of ...
D.W.♦
- 159k
1
vote
1
answer
89
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 ...
D.W.♦
- 159k
0
votes
0
answers
54
views
Could we know what's the total number of unsatisfiable 3SAT formulas for a given n variables?
given some $n$ variables I would be interested to know what is the count of all 3SAT formulas under $n$ that are unsatisfiable.
An example of all 3SAT forumlas under $n=3$ is the following:
$$
( x \...
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. ...
CommunityBot
- 1
0
votes
2
answers
65
views
How could NP-complete problems be in P?
I've learned some basics about P and NP. Please excuse if the following is not very precise.
I've read that NP-complete problems are the hardest problems in NP. (Is that correct?)
But now I'm ...
- 4,247
1
vote
0
answers
63
views
Are there computational complexity results for generative adversarial networks?
First time posting on here; if this question is too rough I would appreciate if you could point me to a stackexchange forum where this question may be a better fit.
Generative adversarial networks (...
- 11
0
votes
1
answer
2k
views
How to prove Exact cover problem is NP Complete using Vertex Cover problem?
Using reduction theorem in NP, we want to prove that Exact cover is NPC by reducing it from Vertex Cover Problem. It is easy to derive it from SAT, but we can't find a solution yet to derive it from ...
- 29.5k
1
vote
1
answer
68
views
Proving 2SAT is in P vs algorithm for finding a satisfying assignment
I want to understand the proof in the following link that 2SAT is in P. What is the need for the last corollary? Wouldn't be enough to just prove the case for the graph with the help of the path ...
- 277k
18
votes
7
answers
5k
views
Would proving P≠NP be harder than proving P=NP?
Consider two possibilities for the P vs. NP problem: P=NP and P$\neq$NP.
Let Q be one of known NP-hard problems.
To prove P=NP, we need to design a single polynomial time algorithm A for Q and
prove ...
CommunityBot
- 1
63
votes
6
answers
26k
views
If everyone believes P ≠ NP, why is everyone sceptical of proof attempts for P ≠ NP?
Many seem to believe that $P\ne NP$, but many also believe it to be very unlikely that this will ever be proven. Is there not some inconsistency to this? If you hold that such a proof is unlikely, ...
CommunityBot
- 1
13
votes
2
answers
14k
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 ...
CommunityBot
- 1
3
votes
0
answers
30
views
Understanding a black-box vs white-box simulation and relativization
I am trying to understand the relativization barrier from Baker Gill Solovay (BGS).
About this barrier, I have heard that it only applies when using a black-box simulation. Hence, my question is, what ...
- 427
65
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 ...
- 103
0
votes
0
answers
82
views
If P = NP then EXP^P = NEXP^NP?
I believe that if P = NP, then that would imply EXP = NEXP (because of the padding argument), and then EXP^P = NEXP^NP (we could replace EXP with NEXP since they are equal, and replace P with NP, ...
- 277k
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 ...
0
votes
1
answer
150
views
P Vs NP can never be proven one way or the other!
Okay, so I was reading a bit about P vs NP problems. And I found out that proving P Vs NP is an NP problem.
And since if we prove that any problem in NP is a P that would mean that we have NP=P.
...
- 1
2
votes
1
answer
98
views
What is the exclusion-inclusion algorithm for TSP?
I was looking at the wikipedia page for the Travelling Salesman Problem and found a reference to another exact algorithm besides Held-Karp that's also $O(2^nn^2)$.
Specifically: "This bound has ...
- 2,348
0
votes
2
answers
159
views
Can we DISPROVE that a problem is NP-complete
So I basically had an exam question in which we were given a problem and we had to prove or disprove that it was in NP-complete. I tried to prove it but could not because apparently it could not be ...
2
votes
2
answers
127
views
What if solving P vs NP revealed a contradiction?
Let's just say that some person discovered that $P = NP$ implies $P \neq NP$ and $P \neq NP$ implies $P = NP$, and we don't know what is causing this contradiction, And this was a valid proof that was ...
1
vote
1
answer
62
views
Is proving NP-(in)completeness generally NP-complete?
Is even distinguishing between NP complete and incomplete problems an NP-hard problem?
- 7,068
-2
votes
2
answers
398
views
If the halting problem is NP hard, would P = NP with a hypercomputer capable of computing the halting problem in polynomial time?
The halting problem is NP hard, to my knowledge any NP problem can be reduced to a NP hard problem. Let us define a new computational complexity class called HP(Hypercomputational polynomal-time), The ...
- 1,227
328
votes
7
answers
159k
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 ...
- 8,248
0
votes
1
answer
82
views
Reduction of np to npc
Given that $A$ is $NPC$ problem. And I need to check "if $D$ belongs to $NP$ and $D\leq_p^\mathsf{}A$ then $D$ is $NPC$" is true or not?
My approach: Since $D\leq_p^\mathsf{}A$, therefore $...
- 29.5k
1
vote
1
answer
47
views
In terms of P=?NP, would a P time solution to Subset-Sum have to work in P time when there is no subset that sums to T in the input?
This question is asking for clarification on what P=?NP is asking specifically. I've read the official problem description: here and it seems like P=?NP is primarily concerned with inputs that result ...
- 8,091
0
votes
1
answer
1k
views
Prove or disprove, If A ≤p B and B is NP-hard, then A is in NP-hard
Intuitively if A can reduce to B, and B is NP-Hard, A might be NP Hard but maybe not. If there is a way to solve A that does not involve reducing to B, it might be faster.
How do I formally disprove ...
CommunityBot
- 1
1
vote
1
answer
108
views
Is $P=NP$ even if we need infinitely many algorithms?
If $P=NP$ was proven with an algorithm, would that have to mean that there is one algorithm that has to work for all inputs of length $n$?
More specifically, what if there were infinitely many ...
- 7,068
1
vote
2
answers
51
views
Does $P=NP$ require an algorithm that uses polynomial space?
if there was an algorithm that runs in polynomial time, but its size requires $O(2^n)$ bits, would that still prove $P=NP$?
- 7,068
-5
votes
1
answer
91
views
Really confused
Suppose there is a language L∈NP, that is not NP-Complete and L≠∅ and L≠Σ∗. Which of the following statements can we infer from this?
P = NP
P ⊊ NP
P ≠ NP
NP ⊆ P
- 11.6k
-4
votes
3
answers
198
views
What is wrong with this argument that if A is NP Complete, but B is in P, then A\B is NP Complete and B\A is NP Complete as well?
The following seems to me to be relevant to this question, but to me is an interesting exercise, especially since I have not formally worked with complexity before, but I want to learn more:
Suppose ...
2
votes
3
answers
382
views
Is there a TM that halts iff P = NP?
Is there a Turing machine that halts iff P = NP? There are Turing machines that halt iff the Goldbach conjecture is false, or the Riemann hypothesis is false. How about the P vs. NP question? This is ...
- 3,075
3
votes
3
answers
151
views
Examples of higher order algorithms ($\mathcal{O}(n^4)$ or larger)
In most computer science cirriculums, students only get to see algorithms that run in very lower time complexities. For example these generally are
Constant time $\mathcal{O}(1)$: Ex sum of first $n$ ...
- 29.5k
1
vote
2
answers
187
views
"Polynomial Counter" Turing Machine
I need some help with this question:
Definition: A Turing-machine that is a counter for the language $L$ is called 'polynomial counter' if there exists a polynomial $p$ s.t. every word $w\in L$ ...
- 29.5k
1
vote
2
answers
103
views
P = NP ==> there exists no OWF: proof using NTM and binary tree
I read a proof in my script:
If $P = NP\implies $ there exists no OWF $f$.
A function $f$ is a OWF $\iff$ $f\in PTIME \space \land$ $f^{-1}\notin PTIME$
Their proof was a bit messy so I want to ask if ...
- 25
0
votes
1
answer
83
views
Assume P != NP, are these assertions valid?
Assume $P \ne NP$, and $A$ is a problem in $P$ and $B$ is a problem which is $NP-complete$.
Are the following assertions valid?
$A \le_{P} B$
$B \le_{P} A$
My approach:
$B \le_{P} A$ isn't valid, ...
- 3
4
votes
3
answers
585
views
How are boolean circuits used for solving P vs NP?
In the paper https://web.stanford.edu/~gavish/documents/sipser-pvsnp.pdf , it is mentioned under the Status section that boolean circuits have been used to try and solve P vs NP. Can anyone explain to ...
1
vote
1
answer
85
views
Proof plan for P ≠ NP
Let $M$ be a Turing Machine for SAT. We want to encode certain paths of $M$ in a very short way in order to diagonalize against the paths.
For each natural number $k$, we will have a formula $\phi$ of ...
- 72.4k
0
votes
1
answer
237
views
The subset sum problem is not in P because the question is about lossy compressed data? Why not?
Where is there a gap or error in my reasoning?
The subset sum problem deals with a set of n numbers, which is the result of lossy compression of an array r of numbers (r = (2^n)-1).
The compression ...
- 14k
4
votes
4
answers
6k
views
Is there any NP-hard problem which was proven to be solved in polynomial time or at least close to polynomial time?
I know this could be a strange question. But was there any algorithm ever found to compute an NP-problem, whether it be hard or complete, in polynomial time. I know this dabbles into the "does P=...
- 121
1
vote
1
answer
100
views
There is an $n^k$ prover if and only if $P = NP$
I am studying computational complexity using Papadimitrious's book: "Computational Complexity".
I am trying to solve the final statement of Problem 8.4.9, but I am stuck and would like some ...
- 13.4k
7
votes
0
answers
70
views
P=NP turns 50. 1971 STOC conference
Stephen Cook presented his seminal paper "The complexity of theorem-proving procedures" at the 1971 STOC (Symposium on Theory of Computing) conference which was held May 3-5, 1971 at Case ...
- 171
5
votes
1
answer
312
views
How to prove that existence of one-way functions implies P≠NP?
Wikipedia:
The existence of such one-way functions... would prove that the complexity classes P and NP are not equal.
How is this proved?
- 7,455
2
votes
1
answer
413
views
Is reduction symmetric?
I was watch this lecture https://youtu.be/moPtwq_cVH8?t=2895, and at this point he says a lot about reductions, take a problem and reduce to another problem. From what I could understand this is a ...
- 277k
1
vote
0
answers
42
views
Show that if vertex cover is reducible to a mod-inverse than P=NP
Let MOD-INVERSE consist of all pairs $\langle N,c \rangle$ such that $c$ has an inverse modulo $N$.
Let VERTEX-COVER consist of all pairs $\langle G,k \rangle$ such that $G$ is an undirected graph ...
- 277k
1
vote
1
answer
238
views
3Col reduction Variation, Special edges
I have a question concerning NP reduction.
My question asks me to show that if I have a graph with Edges that connect 3 nodes together instead of 2, (Y style I assume). I need to prove that finding ...
CommunityBot
- 1
1
vote
1
answer
126
views
$P = NP$, what am I missing?
First post here so hope I'm not missing too many guidelines.
I've had this idea for a few weeks now and I can't myself see where I'm going wrong with it, hope it makes some sense to you and thanks in ...
- 15.6k
0
votes
1
answer
666
views
If P = NP, do these NP-complete problems reduce to these specific easier versions?
I am trying to understand reductions and NP-completeness from Algorithms by Dasgupta et al.
Chapter 8 has the table below and I am wondering:
if $P = NP$ does each of the problems on the left reduce ...
- 2,112
-2
votes
2
answers
568
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
1
vote
2
answers
150
views
If X is in NP then $\overline{X}$ is in NP. True, false or "we don't know"? Why?
If X is in NP then $\overline{X}$ is in NP.
True, false or "we don't know"? Why?
- 30k
1
vote
1
answer
144
views
Must an optimization problem with a greedy algorithm belong to P?
If it is known that for some optimization problem there is a greedy algorithm that solves it and the solution includes sorting of input at the preliminary stage, is it necessarily true that the ...
- 143
-2
votes
1
answer
625
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?
- 39k