The Stack Overflow podcast is back! Listen to an interview with our new CEO.

# Questions tagged [p-vs-np]

The tag has no usage guidance.

158 questions
Filter by
Sorted by
Tagged with
577 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 ...
359 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 ...
648 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: ...
130 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 ...
280 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? ...
149 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?
190 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 ...
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 "...
773 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 ...
157 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 ...
138 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 ...
1k 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.
413 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 ...
199 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 ...
28 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 ...
731 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 ...
820 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 ...
218 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 ...
290 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 ...
122 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 ...
948 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 ...
489 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 ...
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.
243 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 ...
2k views

### What is the simplest known NP-Complete problem for testing P=NP solutions? [closed]

About a year and a half ago I ask this question regarding $P=NP$. The answers have helped me understand the problem tremendously and since then I've dabbled further into the topic. With that stated, ...
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 ...
188 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 ...
107 views

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 ...
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 ...