Questions tagged [p-vs-np]
The p-vs-np tag has no usage guidance.
207
questions
4
votes
2answers
2k views
What is the simplest known NP-Complete problem for testing P=NP solutions? [closed]
About a year and a half ago I asked this question regarding $\mathsf{P}=\mathsf{NP}$. The answers have helped me understand the problem tremendously and since then I've dabbled further into the topic....
0
votes
1answer
93 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.
...
5
votes
3answers
3k 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
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-...
2
votes
2answers
326 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. ...
0
votes
1answer
487 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
129 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 ...
10
votes
4answers
5k 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. ...
2
votes
1answer
81 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 ...
18
votes
7answers
4k 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 ...
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 ...
1
vote
2answers
389 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 ...
0
votes
1answer
205 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 ...
101
votes
5answers
16k 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....
2
votes
1answer
83 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
182 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
492 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 ...
1
vote
1answer
323 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 ...
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 ...
2
votes
1answer
133 views
proving that $P\ne NP$ under an assumption
Suppose that $P^{SAT} \not\subseteq coNP$. Prove that $P\ne NP$.
What I did:
Suppose that $P=NP$. Then, $P = coP = NP = coNP$.
We know that $P^P = P$.
Then, by assumption: $P^{NP} = NP = coNP$
...
1
vote
1answer
97 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?
10
votes
1answer
3k 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 ...
2
votes
1answer
129 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 ...
1
vote
3answers
7k views
What are the implications of P=NP? [duplicate]
Is there a list of implications of $P=NP$?
Presumably, a proof of $P \ne NP$ will be by contradiction, for which a list of consequences of $P=NP$ would be useful.
0
votes
1answer
45 views
Effective Procedures and P vs NP Problem
If, suppose, P doesn't equal NP. Implication of this statement is that there is no effective procedure to solve a hard problem; however there exists an acceptable solution S. I have following two ...
1
vote
1answer
524 views
Why any problem can be reduced to SAT is NP-Complete?
I have a book statement says the title, I don't understand it. From my current understanding if a problem A can be reduced to a problem B then it only means B is at least as difficult as A.
3
votes
2answers
331 views
Given that A reduces to B in $O(n^2)$ and B is solvable in $O(n^3)$, solve A
Suppose a problem A reduce to problem B and reduction is done in $O(n^2)$ time.
If problem B is solved in $O(n^3)$ time then what about the time complexity of problem A?
Approach:
A is reduced to B . ...
0
votes
1answer
262 views
Can we detect perfect matchings in P? in NP? in coNP?
This question concerns the classes P and N P . If you are familiar with them, you may skip the definitions and go directly to the question.
Let L be a set. We say that L is in P if there is some ...
9
votes
0answers
292 views
P vs NP and the Time Hierarchy
Assuming $P\neq NP$, is it possible that there exists a $k$ such that $P\subseteq\textsf{NTIME}(t^k)$?
There reason I ask this is that I assume the following:
$$P=NP \implies \forall k\ \exists j.\ \...
2
votes
1answer
88 views
Are there problems that are DSPACE(O(1)) complete?
I know there are problems that are NL-complete, NP-Complete, PSPACE-complete, etc. Are there problems that are DSPACE(O(1))-complete I.e. NSPACE(O(1))-Complete I.e. Reg-Complete?
Thanks!
1
vote
0answers
129 views
What can be a Zero Knowledge Proof of a working SAT Algorithm?
Me and my colleague are exploring new ideas to solve SAT efficiently (i.e. in polynomial time) and it's the case that there is a candidate algorithm.
Unfortunately, neither of us can write scripts ...
0
votes
1answer
81 views
Does indirect diagonalization a relativize technique?
My main question is can with R.kanon , Fortnow ,... technique that shows lower bounds for SAT seperate P and NP ?
Baker-Gill-Solovay showed that $P?=NP$ could not be solved with relativization. Does ...
3
votes
1answer
806 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), ...
0
votes
1answer
77 views
Are there infinite possibilities to the outcome of the P vs. NP question?
The P vs. NP poll provides 3 possibilities: equal, not equal, and independent. This is reasonable, because despite the law of the excluded middle you must supply a proof for your answer, which itself ...
4
votes
1answer
274 views
Logical characterization of P versus NP problem (and references for least fixed point logic)
Wikipedia says the following (and more) about the logical characterization of the P versus NP problem here:
Thus, the question "is P a proper subset of NP" can be reformulated as "is existential ...
1
vote
1answer
36 views
What's wrong with the following argument that $NP \subset coNP$? [duplicate]
What's wrong with the following argument that $NP \subset coNP$?
let $L \in NP$; then there exists an NTM $N$ that decides $L$ in $f(n)$ time where $f(n) = O(n^k)$ for some natural number $k$.
...
6
votes
2answers
215 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 ...
2
votes
1answer
486 views
P vs NP problem (Student example)
Hello dear stackexchangers,
I have a simple question, and I would like to say that I am not a scientist. When I read the problem statement on this link: http://www.claymath.org/millennium-problems/p-...
2
votes
2answers
398 views
P vs NP and can an oracle make P=EXPTIME?
As I understand, diagonalization cannot be used to prove or disprove P vs NP, because for some oracle $A$, $P^A = NP^A$, whereas under another oracle $B$, $P^B \neq NP^B$.
I don't fully understand ...
0
votes
1answer
66 views
Independence Implies P $\ne$ NP
Suppose P vs. NP is independent of ZFC. Then there cannot be an efficient SAT solver, otherwise it would constitute a proof for P = NP. Therefore P $\ne$ NP.
What we see here is that independence ...
8
votes
2answers
828 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$ ...
3
votes
2answers
235 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 ...
2
votes
2answers
346 views
Is every problem in NP?
My friend and I were studying NP-hard problems and NP-completeness. I don't think we have understood the concept very well so I thought I would come here to solve our doubt.
To show that a given ...
0
votes
0answers
873 views
Show that P is a subset of NP
Okay, before I start with the question I would like to point out that I am aware that there are many proofs of this question online. However, I am interested in showing this with the definitions of my ...
2
votes
1answer
45 views
Analysing the algorithm of a language called CONNECTED in Sipser to show that it belongs to class P
The question and its answer is given in the following picture:
But I do not understand why stage 2 causes at most $n+1$ repetitions, and why stage 3 uses at most $O(n^2)$ steps, and I understand that ...
1
vote
2answers
780 views
if traveling salesman problem is decidable in polynomial time, can an actual solution be proposed in polynomial time?
I'm asking because it seems that P problems refer to decision problems rather than actually propose a solution.
8
votes
0answers
260 views
Are there consequences for P ā NP that are unintuitive?
It's often regarded that the most intuitive answer to the question of $P$ vs $NP$ is that $P ā NP$. This is often illustrated with some consequences that would follow if $P = NP$ were true. Things ...
