Questions tagged [p-vs-np]
The p-vs-np tag has no usage guidance.
233
questions
0
votes
0
answers
9
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 (...
- 1
1
vote
1
answer
27
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 ...
- 113
2
votes
0
answers
14
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 ...
- 307
0
votes
0
answers
35
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, ...
2
votes
2
answers
99
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 ...
- 99
2
votes
1
answer
34
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 ...
0
votes
2
answers
87
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 ...
- 1
1
vote
1
answer
48
views
Is proving NP-(in)completeness generally NP-complete?
Is even distinguishing between NP complete and incomplete problems an NP-hard problem?
- 161
-2
votes
2
answers
143
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 ...
- 99
0
votes
1
answer
21
views
Understanding P, NP with an example decision problem
I was reading the definitions of p vs np in [this post] (What is the definition of P, NP, NP-complete and NP-hard?) and I was wondering about how to classify the example decision problem where you ...
- 3
0
votes
1
answer
41
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 $...
- 1
1
vote
1
answer
42
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 ...
1
vote
1
answer
92
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 ...
user136613
1
vote
2
answers
45
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$?
user136613
-5
votes
1
answer
71
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
-4
votes
3
answers
96
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 ...
1
vote
2
answers
92
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
1
vote
2
answers
101
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$ ...
- 13
0
votes
1
answer
73
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, ...
1
vote
1
answer
72
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 ...
- 169
0
votes
1
answer
58
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 ...
- 33
4
votes
4
answers
4k
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=...
- 57
1
vote
1
answer
88
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 ...
- 225
7
votes
0
answers
52
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
4
votes
1
answer
105
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?
- 413
2
votes
1
answer
107
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 ...
- 219
1
vote
0
answers
34
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 ...
- 31
1
vote
1
answer
116
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 ...
- 13
0
votes
1
answer
183
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 ...
- 649
-2
votes
2
answers
174
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 ...
- 11
1
vote
1
answer
65
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
1
vote
1
answer
114
views
Understanding P vs NP
I want to make sure my understanding on P vs NP is correct. I know that NP-complete problems cannot be solved in polynomial time, and if P != NP, then all problems in NP cannot be solved in polynomial ...
- 65
0
votes
0
answers
36
views
How can I prove the following problem is NP?
Because of the covid-19 pandemic, our firm works semi-remote working. We want to that:
Every day 2/5 of staff should be in the office.
Everyone should go to the office 2 times a week.
Teams want to ...
1
vote
1
answer
133
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 ...
- 11
2
votes
2
answers
87
views
proving that a problem is in P
I read online that this problem is in P:
Problem = {a^n, where n is a primary number}
I can't find any algorithm that decides if a word w in ...
asmal
2
votes
3
answers
227
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 ...
- 824
4
votes
3
answers
140
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$ ...
- 519
0
votes
1
answer
134
views
Classification and complexity of generating all possible combinations: P, NP, NP-Complete or NP-Hard
The algorithm needs to generate all possible combinations from a given list (empty set excluded).
...
- 13
0
votes
2
answers
137
views
How would it be possible that primality testing is in P, but not factorization?
Suppose that P != NP. Then there exists 3SAT formulas such that their satisfiability is computationally "evil" (i.e, the satisfiability can be exponentially hard to determine in the size of ...
- 683
-1
votes
1
answer
155
views
What are the practical examples of Semidecidable problems? Is NP problem a semidecidable problem?
I am going through a Turing machine topic. I know about decidable, semi decidable, and decidable problems. But honestly speaking, I did not get any practical examples of Semidecidable problems. Can ...
- 168
0
votes
1
answer
36
views
P vs NP characterization confusion
I know that $P \subseteq NP$, but for a problem in $P$, e.g. MST in a graph, is it a correct statement to say that:
The MST problem belongs in NP-Class.
(I mean, i think it is correct, but could ...
- 133
2
votes
1
answer
942
views
If P=NP, does this imply that all problems are NP-hard?
A problem is said to be NP-hard if every problem in NP is reducible to that problem in polynomial time.
Hence, if P=NP, wouldn't that imply that every problem in NP is reducible to every possible ...
1
vote
1
answer
65
views
While number can be checked for primality in O(n^0.5) then why was it considered to be not in P until AKS test?
While a basic algorithm to check for primality of a number 'n' [checking if a divides n for all a less than n] would take O(n), AKS test was the breakthrough after which it was placed in P complexity ...
3
votes
1
answer
567
views
Does P = NP in Cellular Automata of Hyperbolic Spaces?
I read a few years ago in this book that NP problems are tractable in the space of cellular automata in the hyperbolic plane. What does this mean? Does P = NP ...
- 1,873
-1
votes
3
answers
347
views
Why don't passwords prove P != NP?
Pardon my ignorance on the matter but,
Verifying passwords = Polynomial (linear)
Guessing passwords = Exponential
Since each guess has nothing to do with one another, exponential time is best possible ...
21
votes
4
answers
3k
views
How hard would it be to state P vs. NP in a proof assistant?
GJ Woeginger lists 116 invalid proofs of P vs. NP problem. Scott Aaronson published "Eight Signs A Claimed P≠NP Proof Is Wrong" to reduce hype each time someone attempts to settle P vs. NP. ...
- 325
0
votes
0
answers
47
views
Is a or free SAT formula NP complete?
Let $L$ be the languague which contains all satisfiable formulas which do not have the or symbol $\lor $.
Or more precise $$L=\{\phi | \phi \text{ is a satisfable formula which is only using the ...
- 147
0
votes
2
answers
271
views
If we prove that there is an NP-complete problem that is P, Can we consider that P=NP?
I discover this in All NP problems reduce to NP-complete problems: so how can NP problems not be NP-complete?
If problem B is in P and A reduces to B, then problem A is in P.
Problem B is NP-complete ...
1
vote
2
answers
125
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?
- 31
-2
votes
1
answer
241
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