Questions tagged [p-vs-np]
The p-vs-np tag has no usage guidance.
224
questions
0
votes
1answer
17 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 ...
0
votes
1answer
29 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
vote
1answer
36 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
1answer
84 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 ...
1
vote
2answers
41 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$?
-5
votes
1answer
66 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
3answers
90 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
2answers
82 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 ...
1
vote
2answers
81 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$ ...
0
votes
1answer
72 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
1answer
68 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 ...
0
votes
1answer
52 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 ...
4
votes
4answers
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=...
1
vote
1answer
82 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 ...
7
votes
0answers
45 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 ...
4
votes
1answer
77 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?
2
votes
1answer
50 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 ...
1
vote
0answers
27 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 ...
1
vote
1answer
111 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 ...
0
votes
1answer
75 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
votes
2answers
119 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 ...
1
vote
1answer
48 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 ...
1
vote
1answer
82 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 ...
0
votes
0answers
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
1answer
76 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 ...
2
votes
2answers
83 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 ...
2
votes
3answers
200 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 ...
4
votes
3answers
137 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$ ...
0
votes
1answer
100 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).
...
0
votes
2answers
124 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 ...
-1
votes
1answer
111 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 ...
0
votes
1answer
29 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 ...
2
votes
1answer
562 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
1answer
58 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
1answer
542 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
votes
3answers
295 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 ...
20
votes
4answers
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. ...
0
votes
0answers
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 ...
0
votes
2answers
186 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
2answers
108 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?
-2
votes
1answer
171 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?
0
votes
2answers
61 views
How to prove P = NP if problem Π ϵ NP-complete and Problem complement Πc ϵ NP?
How to prove if P = NP if problem Π ϵ NP-complete and Problem complement Πc ϵ NP?
OR
P = NP if NPC intersects with Co-NPC
1
vote
1answer
57 views
What is and amplification factor in pseudo-random generators?
I can't seem to find an answer to this. For instance, I have this question:
Show that, if $P=NP$, there aren't any pseudo-random generators (even with amplification factor $n+1$).
My gut tells me this ...
-1
votes
2answers
226 views
Review my proof that Co-NP != P
This is hobby level work, not my job. I wrote this excerpt to share some ideas about Co-NP.
The idea is to pick a problem category in Co-NP, where the correct answer is hard to verify because of ...
0
votes
3answers
60 views
Is it possible that Co-NP = P but NP != P
Suppose there exists an algorithm that takes as input an unsatisfiable SAT formula, and never fails to verify it in polynomial time. However, when the input is a satisfiable formula, it doesn't work (...
1
vote
1answer
66 views
P=NP when number of inputs that give 1 is bounded by polynomial
Suppose there exists some NP-complete problem such that the number of inputs that gives 1 as an output is bounded by a polynomial; that is, if the problem is $f \colon \{0, 1 \}^* \to \{0, 1\}$, then, ...
2
votes
1answer
73 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 ...
2
votes
2answers
357 views
P vs NP and Angle Trisection (serious question)
I have a question. Please be nice; I come from the corporate world and my knowledge of computer theory is around a college freshman level.
My understanding from many popular-level sources (like Scott ...
0
votes
0answers
65 views
How sub-exponential time does $\text{3SAT}$ have to be to make $\text{NP} \neq\text{EXP}$? What else would imply $\text{NP} \neq\text{EXP}$?
The exponential-time hypothesis posits that if $\mathsf{3SAT}$ has NO subexponential time algorithm (i.e. one in $\mathcal O(2^{o(n)})$), then $\mathsf{P}\neq \mathsf{NP}$.
However, I am interested ...
0
votes
1answer
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 ...