# Questions tagged [p-vs-np]

The tag has no usage guidance.

154 questions
Filter by
Sorted by
Tagged with
3answers
94 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 ...
7answers
111k 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 ...
1answer
138 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 ...
3answers
424 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 ...
1answer
87 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 ...
1answer
64 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. ...
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 ...
1answer
96 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$ ...
1answer
82 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 ...
0answers
26 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?
1answer
2k 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 ...
1answer
60 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 ...
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 ...
3answers
2k 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.
1answer
35 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 ...
1answer
136 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.
2answers
67 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 ...
1answer
52 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 ...
5answers
14k 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....
0answers
269 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.\ \...
1answer
69 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!
0answers
65 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 ...
1answer
62 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 ...
1answer
328 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), ...
1answer
65 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 ...
1answer
178 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 ...
1answer
35 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$. ...
2answers
182 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 ...
1answer
283 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-...
2answers
369 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 ...
1answer
50 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 ...
2answers
743 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$ ...
2answers
122 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 ...
2answers
163 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 ...
0answers
342 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 ...
1answer
28 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 ...
2answers
337 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.
0answers
195 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 ...
2answers
332 views

### Naive argument that P ≠ NP

Consider the following naïve argument that any algorithm solving SAT must take $\Omega(2^n)$ time in the worst-case scenario. Let $f(x_1,x_2,\dots,x_n)$ be a Boolean function in conjunctive normal ...
0answers
24 views

### NP-Hard for resolving P=NP [duplicate]

Im studing complexity theory and im reading this question on Quora. According to what the guy is saying : if we are able to solve a NP-Hard problem in polynomial time we have prooved that P=NP. But, ...
1answer
228 views

### Solving diophantine equations — does having a bound on the size of the solution help?

Let's define the following languages over the alphabet $\Sigma=\{0,1\}$: H10 is the language of all strings that are encoding of diophantine polynomial equation with integer coefficients and $n$ ...
1answer
193 views

### Could a scientist make money off of the P vs. NP solution?

If someone solved the P vs. NP problem, would they be able to keep it a secret and make money off of it by, say, starting a software or security company? Or would they only be able to publish it for ...
5answers
5k views

### Flaw in my NP = CoNP Proof?

I have this very simple "proof" for NP = CoNP and I think I did something wrongly somewhere, but I cannot find what is wrong. Can someone help me out? Let A be some problem in NP, and let M be the ...
9answers
8k 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 ...
2answers
1k views

### P=NP, isn't it?

Cook and Levin showed in 1971 how deterministically in polynomial time from every non deterministic Turing machine M, that halts in polynomial number of moves/steps, and string w to create the boolean ...
2answers
162 views

### Computational Complexity and P vs. NP, A New Insight [closed]

There is a preprint on arXiv that states (in my own words). If there are three numbers (digits) and task is to add all three numbers. First we well take two number to add, set aside third number. ...
1answer
42 views

### Solve Time Complexity problem using Time Hierarchy

I am trying to understand Time Hierarchy. I have an example that is solvable using the rules of Time Hierarchy. I would like an explanation on how to solve so that I may understand better how to use ...
0answers
87 views

### Consequences from a lower bound of SAT problem

I'm not sure how lower bounds affect the question to the P=NP problem. I.e. : Let a SAT instance with a size of n be transformed into an instance of a problem X with a size of n3. If you find a ...
6answers
21k 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, ...
1answer
139 views

### Why doesn't descriptive complexity theory solve P = NP?

According to the Wikipedia page on Descriptive complexity theory: In the presence of linear order, first-order logic with a least fixed point operator gives P, the problems solvable in ...