Questions tagged [p-vs-np]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1
vote
2answers
379 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
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, ...
2
votes
1answer
248 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$ ...
-3
votes
1answer
457 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 ...
14
votes
5answers
6k 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 ...
59
votes
9answers
10k 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 ...
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 ...
0
votes
2answers
170 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
55 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
121 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 ...
59
votes
6answers
23k 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, ...
3
votes
1answer
181 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
69 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
51 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
185 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 ...
0
votes
1answer
937 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
411 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 ...
-1
votes
2answers
142 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
396 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? If $NP=...
0
votes
0answers
133 views

How not to prove that P ≠ NP implies NP ≠ PSPACE

Let's define the two variants of the Travelling salesman problem: $TSP_{opt}$ : Give me the shortest tour $TSP_{dec}$ : Is there a tour of $l$ or shorter (Yes/No) Now assume $P \neq NP$: Since $...
7
votes
2answers
1k views

Polytime algorithm for SUBSET-SUM assuming P=NP

In the Wikipedia page on P vs. NP problem there is an algorithm that "solves" SUBSET-SUM in case P=NP in polynomial time. (It's idea is to find a TM that gives a certificate). But it gives "yes" in ...
2
votes
1answer
177 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?
3
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 "...
0
votes
2answers
282 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 ...
8
votes
1answer
855 views

What is wrong with this conditional proof of P=NP?

I have recently thought up the following proof that L=P implies P=NP. Suppose L=P. Let A be a problem in NP. By the verifier definition of NP, each positive solution to A has a witness that can be ...
1
vote
0answers
246 views

Is valid the notion of infinity for the NP-complete problems?

We have defined two complexity classes which have a close relation with the notion of infinity. The first one is: We say that a language $L$ belongs to $UP_{\infty}$ if there exist an infinite ...
2
votes
2answers
175 views

Is P = NP when solutions length is polynomially bounded by instance length?

I'm currently reading the book "P, NP, and NP-Completeness" by Oded Goldreich. I'm currently reading a chapter that's concerned with the "search version" of the P-vs-NP-problem, that is if finding ...
2
votes
2answers
2k views

co-NP but not NP problems

What are the problems that are in co-NP but not in NP? i.e, those problems where incorrect strings can be deterministically verified in polynomial time but the correct strings can't be.
0
votes
2answers
632 views

If P = NP, then how not cannot solve NP-hardness (the one that doesn't intersect with NP-complete) in polynomial-time?

My question is that if P = NP, then we can solve any NP-hard problems (the one which is NP-complete and the one which is not-NP-complete) by saying that since we have a polynomial time algorithm to ...
4
votes
2answers
208 views

Is there a fundamental reason/limitation, such as $P \not = NP$, that prevents computers from being able to do mathematics (proofs, etc.)?

I'm a student, so I apologise if this is an idiotic question: Is there a fundamental reason/limitation, such as $P \not = NP$, that prevents computers from being able to do mathematics (posing ...
0
votes
0answers
29 views

Is this line from the rational wiki p vs np bit correct? “ A computational problem is considered ”in P [duplicate]

http://rationalwiki.org/wiki/Pseudomathematics#P_vs._NP_problem A computational problem is considered "in P" if an algorithm exists that can solve the problem in "polynomial time" — that is, it's ...
9
votes
1answer
403 views

If one shows that UNIQUE k-SAT is in P, does it imply P=NP?

Valiant & Vazirani proved SAT is reducible to UNIQUE SAT under randomized probabilistic reductions in polynomial time. Calabro et al. showed that UNIQUE k-SAT is as hard as k-SAT. Now the ...
6
votes
2answers
884 views

Is detecting easy instances of NP-hard problems easy?

My question is the following. Assume that $\Pi$ is an NP-hard problem. Given an arbitrary instance $I$ of $\Pi$ and assume that an adversary knows that this instance is easy to solve, is it possible ...
4
votes
2answers
271 views

“P may collapse” vs. Time hierarchy theorem

https://en.wikipedia.org/wiki/P_versus_NP_problem states: If graph isomorphism is NP-complete, the polynomial time hierarchy collapses to its second level. They further state that this may be ...
3
votes
1answer
460 views

Why does a reduction from a P-problem to an NP-complete problem not show that P=NP?

Consider the following problem, called BoxDepth: Given a set of $n$ axis-aligned rectangles in the plane, how big is the largest subset of these rectangles that contain a common point? Say we ...
5
votes
1answer
264 views

Stronger versions of P != NP which better express actual convictions

Does the conviction "L-uniform NC1 != NP is incredibly hard to prove!" express the core of "P != NP is incredibly hard to prove!" in a similar spirit as the conviction "The polynomial hierarchy doesn'...
0
votes
1answer
123 views

Is following observation on Ladner's theorem correct?

Suppose $NP\subseteq DTIME[n^{f(n)}]$ where $f(n)$ is any function satisfying $\omega(1)$ then is it true $P=NP$ holds? Ladner's theorem states infinite time hierarchy between $P$ and $NP$. That is ...
7
votes
1answer
1k views

Why the need for TSP solvers when there are SAT solvers?

Concorde TSP is a solver for TSP. SAT solvers are solvers for boolean satisfiability. TSP and SAT are NP-complete. Hence, why spent the time to develop Concorde TSP when there is an abundance of SAT ...
6
votes
1answer
499 views

Why can't we exploite finiteness to prove incompleteness in NP?

It is well established that the class of recursive languages is strictly contained in the class of recursively enumerable languages (Rec $\ne$ RE). Any finite language is decidable and hence can not ...
6
votes
1answer
260 views

Is there a philosophical counterpart question to P != NP?

Gödels motivation to prove his incompleteness theorems was the philosophical statement "This sentence is wrong.". Is there a philosophical counterpart to the statement P != NP? For example such ...
3
votes
3answers
3k views

Does a polynomial solution for an NP-complete problem that can only be implemented for small N *still* imply P=NP?

Basic sanity check on NP-complete solutions: Suppose there was a polynomial time solution for an NP-complete problem, but the size of NP-complete problems that could be solved is still relatively ...
7
votes
1answer
211 views

How to use an old SAT solver to discover a new one, as is done in The Golden Ticket?

In Lance Fortnow's book The Golden Ticket, he mentions that once you have a polynomial-time algorithm for an NP-complete problem, you can use it to find a faster algorithm. Can you tell me how that is ...
4
votes
2answers
151 views

What happens to quantum algorithms such as BB84 if P=NP

Under the hypothesis that P=NP, many cryptographic protocols are no longer secure (i.e. attacks are feasible). The BB84 algorithm is based on the idea that by observing a quantum state, one has to (...
0
votes
0answers
115 views

If NP is easy on average then does it mean P=NP?

If $NP=RP$ then $NP$ is easy on average. Then from point $1$ in abstract in http://lance.fortnow.com/papers/files/derand.pdf which says $NP$ is easy on average implies $P=BPP$ do we have $NP=RP\...
5
votes
6answers
1k views

How is it valid to use oracles in mathematical arguments?

Oracles do not exist. If one did exist, then you would replace them with a subroutine with computational requirements and you would no longer need an "Oracle". Thus, Oracles do not exist almost by ...
5
votes
0answers
54 views

Is anything known about the structure of sets of valuations representable by 3CNF formulas?

Let's suppose we have propositional variables $x_1 ... x_n$. A valuation is an assignment $v$ s.t. $v(x_i)$ is an element of $\{false, true\}$ for $1 \leq i \leq n$. So, there are $2^n$ possible ...
6
votes
1answer
13k views

Proving that if coNP $\neq$ NP then P $\neq$ NP

I am new in complexity theory and this question is a part of a homework that I have and I am stuck on it. Let ${\sf coNP}$ be the class of languages $\{\overline{L}: L \in {\sf NP} \}$. Show that if $...
0
votes
0answers
42 views

What is an example of a problem that is in NP - P, but not NPC? [duplicate]

Assuming $P \neq NP$, I expected that $NP - P \subset NPC$, but from the diagram on Wikipedia it appears to not necessarily be true. What is an example of a problem that is complex enough to be in $...
13
votes
2answers
8k views

How to prove P$\neq$NP?

I am aware that this seems a very stupid (or too obvious to state) question. However, I am confused at some point. We can show that P $=$ NP if and only if we can design an algorithm that solves any ...
0
votes
1answer
115 views

3SAT with an oracle for expanding the clauses

Let's consider 3SAT, so we have clauses like: (A or B or C) and (A or not B or D) and ... If we distribute the "and" over the first two clauses, we get the disjunction of: ...