Questions tagged [p-vs-np]
The p-vs-np tag has no usage guidance.
194
questions
19
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
36 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
68 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 ...
0
votes
0answers
22 views
$NP$ is not in $P(n^k)$ for any fixed $k \geq 1$
I encountered this problem which asks to show that for any fixed $k \geq 1$, $NP$ is not contained in $P(n^k)$...
As an attempt, I thought of using the time hierarchy theorem which says that there ...
-2
votes
0answers
37 views
-3
votes
0answers
38 views
If A ∉ NP then A ∈ co-NP. True, false or we don't know?
If A ∉ NP then A ∈ co-NP.
True, false or we don't know?
0
votes
1answer
39 views
If X is polynomial-time reducible to Y and X is polynomial-time reducible to Z then Y is polynomial-time reducible to Z?
If $X$ is polynomial-time reducible to $Y$ and $X$ is polynomial-time reducible to $Z$,
$Y$ is polynomial-time reducible to $Z$?
If $X \leq_p Y$ and $X \leq_p Z$ then $Y \leq_p Z$?
True, false or we ...
-1
votes
1answer
34 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?
-3
votes
1answer
36 views
If X is polynomial reduction to Y and Y is in NP, then X is in NP?
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?
-1
votes
2answers
49 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
45 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
205 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
43 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
59 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, ...
1
vote
1answer
42 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
350 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
24 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
340 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 ...
0
votes
1answer
82 views
Prove or Disprove, 3SAT ≤p 2SAT, then P = NP
I know that 3SAT is in NP and 2SAT is in P. And 2SAT can reduce to 3SAT just says 3SAT is strictly harder than 2SAT, so I don't think this proves P = NP, but it doesn't seem to disprove it either.
2
votes
1answer
202 views
Would a sparse NP-Complete language imply L = NP?
Would a sparse NP-Complete language imply L = NP?
Update: Thanks to Noah Schweber for clear and comprehensive answer. Having thought about it more, one would need a logspace reduction from NP-...
7
votes
1answer
867 views
Algorithms that run in polynomial time if P=NP
On Wikipedia, it says that that there are some algorithms that would run in polynomial time if and only if P=NP. They gave one example (without citation), but are there any others? I tried looking ...
0
votes
1answer
28 views
If there is an polynomial time approximation to an NP-complete problem, is P approximately NP?
Deciding bipartite hypergraph coloring is NP-hard:
While for bipartite graphs a 2-coloring can be found in linear time, it was shown by Lovasz [10] that the problem to decide whether a given k-...
1
vote
1answer
72 views
Time complexities of state-of-the-art SAT solvers with respect to length of the formula
I am learning about DPLL and CDCL SAT solvers, and I know that they have time complexity exponential to the number of variables.
If I am not mistaken, one of the reasons why most believe P does not ...
1
vote
3answers
66 views
NP-complete problem 3-SAT, is there a difference in complexity between just providing yes/no without exact solution
The 3-SAT problem is NP-complete, meaning that no known algorithm can provide an exact solution in polynomial time, while a solution can be tested very quickly in polynomial time.
My question is, ...
-1
votes
1answer
121 views
Showing on-line P = NP
I have developed a theorem that proposes a method to build algorithms. All the algorithms produced by this method are in P ... they never go up to more than $6(n^{12})$ operations.
Following that, I ...
24
votes
5answers
8k views
P = NP clarification
Let's use Traveling Salesman as the example, unless you think there's a simpler, more understable example.
My understanding of P=NP question is that, given the optimal solution of a difficult problem,...
1
vote
1answer
2k views
A problem in NP but not NP-complete?
Graph isomorphisim is not proven to be NP-complete what would it imply if it were possible to prove that there are some problems which are in NP set of problems but not in NP-complete set.
0
votes
1answer
50 views
how to proof ${ NPC \bigcap CO-NPC \ne \varnothing then NP = P ? }$
how proof ${\ \ NPC \ \ \bigcap \ \ CO-NPC \ne \varnothing }$ then
${NP = P ? }$
2
votes
1answer
64 views
How to know if a problem belongs to NP Class?
What I know (NOT strictly speaking): I know that there is an open question about the equality of P and NP Classes and as long as there is no known algorithm that solves NP problems in P time then we ...
0
votes
1answer
86 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.
...
0
votes
1answer
48 views
Does computational complexity theory take into account problems with subjectivity in the verification of a solution?
When we discuss P vs NP we are looking at the difference between problems that are easily solved versus easily verified (wrt polynomial vs exponential time).
But in both cases these are black-and-...
4
votes
3answers
2k views
If a problem is in P solved via dynamic programming, is it also in NP?
So I can solve a given problem using dynamic programming in $O(n^2k^2)$ time complexity. This means that the problem is in P. But I am asked if it is in NP.
My answer is, "Since it is also polynomial ...
0
votes
1answer
353 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 ...
0
votes
1answer
125 views
Is this statement of P = NP in Agda correct?
Looking for a self-contained statement of P = NP in type theory, I stumbled upon this short Agda formalization (a cleaned up version is reproduced below).
The statement here does seem to express the ...
1
vote
0answers
36 views
Weaker conjectures to prove in order to arrive at P =/= NP
We know we have a long way to go before we come to a proof of P $\neq$ NP. We also know that this road is studded with minor conjectures that will have to be proved/disproved in order to arrive at the ...
2
votes
1answer
65 views
How is $\text{PCP}[O(\log n),O(1)]$ NOT P?
As a prover, we just try to convince the verifier that it's correct, no matter whether it is or not. So we can just analyze every possible route.
For $\text{PCP}[O(\log n),O(1)]$, won't there just be ...
0
votes
0answers
43 views
Confusion about P versus NP [duplicate]
I'm sure that in my following question my reasoning is extremely simplistic and flawed, but I think if someone answered this it would help me understand what the P vs NP conundrum is. So here is my ...
0
votes
1answer
181 views
Baker, Gill, Solovay - construction of oracle B such that P^B != NP^B
I have some questions about Baker, Gill, Solovay proof of the existence of an oracle such that P^B != NP^B. The proof can be found in Siam Journal of Computing, 4:432-442, 1975 [219].
Why Isn't this ...
1
vote
2answers
305 views
P/NP - Polynomial Reduction vs Certificate
I am learning about the P/NP problem right now, and I don't understand when to use polynomial reduction and when to use a certificate.
How I understand polynomial reduction is that you can use it to ...
2
votes
1answer
74 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 ...
3
votes
3answers
167 views
Is the P vs NP problem, an NP or co-NP problem?
A few years ago, a youtube channel named hackerdashery, made an extraordinary youtube video explaining P vs NP, in a semi-vulgarized way :
https://www.youtube.com/watch?v=YX40hbAHx3s
At 7 minutes ...
-1
votes
3answers
480 views
One-way Trapdoor Function
Do the functions of the collatz conjecture and their inverses model a Trapdoor Function?
If given a, b, a^-1, b^-1 and your choice of f(x), is it “hard in the average case” to find some secret x?
I ...
8
votes
2answers
300 views
P vs. NP and Godel's Theorems
This post is based loosely on a previous post, but the presentation is somewhat different and hopefully much more succinct.
Basically, I'm wondering if it is plausible for there to be a formal proof ...
1
vote
1answer
244 views
P vs NP question from GeeksforGeeks
From here: https://www.geeksforgeeks.org/algorithms-np-complete-question-2/
Let S be an NP-complete problem and Q and R be two other problems not known to be in NP. Q is polynomial time reducible to ...
2
votes
2answers
273 views
What's the flaw in the P != NP proof in the article “The Computational Complexity of the Traveling Salesman Problem”
I am reading through some proof of inequality of P and NP
but they are not accompanied by the flaws in the reasoning so I'm trying to find them by myself, just to see if I'm getting the logic right. ...
10
votes
2answers
4k views
Contradiction proof for inequality of P and NP?
I'm trying to argue that N is not equal NP using hierarchy theorems. This is my argument, but when I showed it to our teacher and after deduction, he said that this is problematic where I can't find a ...
1
vote
1answer
95 views
A tricky P=NP problem
Define an operator $\pi(\cdot)$: for a language $L$, $\pi (L)$ is the set of all prefixes of strings in $L$ with length at least half of the original string. Prove that if $\mathsf{P}$ is closed under ...
0
votes
0answers
28 views
Reducing SAT to a P problem in polinomial time [duplicate]
Does reducing SAT in polynomial time to a P problem would mean that P = NP?
2
votes
1answer
120 views
What is Ironic complexity? What are some good resources to learn about it?
The term "Ironic complexity" was coined by Scott Aaronson for the stuff Ryan Williams does in the area of complexity theory. Could anyone tell me what kind of problems and approaches does Ryan ...
7
votes
1answer
2k views
If graph isomorphism is in P, is then P = NP?
I think that, since graph isomorphism is not known to be $\textbf{NP}$-complete, we can not reduce all problems in $\textbf{NP}$ to it, and therefore the implication does not hold.
Additionally, in ...
