Questions tagged [p-vs-np]
The p-vs-np tag has no usage guidance.
4
votes
2answers
2k 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 ...
0
votes
0answers
24 views
3-DNF $\rho$ falsifiable
I am trying to show that following promise problem is solved in polynomial time then P=NP.
Given a 3-DNF $\phi$
$YES$ instance if $\phi$ is falsifiable.
$No$ instance $\phi$ is such that ...
1
vote
1answer
73 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
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?
2
votes
1answer
42 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 ...
5
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 ...
0
votes
1answer
25 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
60 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
49 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 ...
0
votes
1answer
38 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 ...
2
votes
1answer
61 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
40 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
58 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 ...
1
vote
1answer
252 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
59 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 ...
1
vote
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$.
...
6
votes
2answers
178 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 ...
1
vote
1answer
245 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-...
4
votes
1answer
147 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 ...
2
votes
2answers
357 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
44 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
714 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$ ...
2
votes
2answers
95 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
147 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
257 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
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 ...
1
vote
2answers
272 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
172 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 ...
0
votes
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, ...
-4
votes
1answer
157 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 ...
2
votes
1answer
206 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$ ...
1
vote
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 ...
1
vote
2answers
292 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 ...
0
votes
2answers
161 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. ...
0
votes
1answer
41 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 ...
0
votes
0answers
83 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 ...
2
votes
1answer
121 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 ...
3
votes
1answer
42 views
Could a modification of Krom's proof system be used to solve 3-SAT in polynomial time?
A literal is a nonzero integer, and we define $\sim x = -x$.
A clause is a nonempty set of literals.
A CNF is a set of clauses.
A K-rule is a pair $(F,C)$ where $F$ is a CNF and $C$ is a clause.
A ...
0
votes
1answer
42 views
Given an integer n, print all integers from 1 to 2^n. Why does this not prove that P!=NP? [duplicate]
I only just recently learned about the P=NP problem in introduction to algorithms class, and I'm still trying to wrap my head around it. I thought of this situation while cleaning my room today and ...
1
vote
0answers
150 views
If an NP problem is shown to have an exponential lower bound, would that prove that P != NP? [closed]
The Cook-Levin theorem shows that any NP problem is reducible to an NP-complete problem.
Therefore if a polynomial-time algorithm for an NP-complete problem is found, it will mean that all problems ...
54
votes
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, ...
2
votes
1answer
88 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$
...
0
votes
1answer
475 views
If P=NP, which two languages are NOT NP-complete?
In my last exam this question got asked and i just cant find a clear answer:
If P=NP, which two languages are NOT NP-complete?
So I assume there are two special languages, but which?
Thanks in ...
5
votes
2answers
340 views
Why does this not prove $P\neq NP$?
Fiorini, Massar, Pokutta, Tiwary and De Wolf (Exponential Lower Bounds for Polytopes in Combinatorial
Optimization, Journal of the ACM 62(2):article 17, 2015; PDF, ArXiv) show any linear program that ...
6
votes
2answers
579 views
What is the utility of proving P=NP if we can't find an algorithm that can solve any NP problem in polynomial time?
Here we see a very interesting attempt to show that $\mathrm{P} \ne \mathrm{NP}$ by Norbert Blum.
Here we see 116 previous attempts at solving P vs. NP.
Here we see the P vs NP problem defined as:
...
-1
votes
2answers
127 views
Does this problem offer any insight into $P$ vs $NP$
What is the input of a given hash?
The problem can be verified in polynomial time (using a hash that executed in polynomial time), and I suspect that it may be possible to prove that there is ...
1
vote
1answer
233 views
Is the complement of MAX-CLIQUE in NP?
Let $$MAX-CLIQUE = \{\ <G,k>\ |\ G\ is\ an\ undirected\ graph,\ and\ the\ largest\ clique\ of\ G\ has\ k\ vertices\}$$
Does $MAX-CLIQUE\in coNP$? If it does, can you think of a verifier?
...
2
votes
1answer
116 views
Could be solved a NP-complete problem in constant time?
Under the assumption that P would be equal to NP, it could exist a NP-complete problem that is solved in constant time?
0
votes
2answers
178 views
Why can there be no reductions from NP-complete problems to P problems under P ≠ NP
Under the assumption that $P \ne NP$, why is it impossible to reduce a problem that is known to be NP-complete to a problem that is known to be of polynomial time complexity? What kind of fundamental ...
4
votes
2answers
1k views
Having problem understanding the formal definition of NP
So I'm having a tad bit of a problem deciphering the formal definition of NP. In my text book (Algorithm Design, Tardos et al) it says that a problem $X$ belongs to $NP$ iff;
there exists a "...
