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.

Filter by
Sorted by
Tagged with
0
votes
1answer
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 ...
5
votes
2answers
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 ...
6
votes
2answers
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: ...
-1
votes
2answers
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 ...
1
vote
1answer
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? ...
2
votes
1answer
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?
0
votes
2answers
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 ...
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 "...
8
votes
1answer
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 ...
1
vote
0answers
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 ...
2
votes
2answers
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 ...
2
votes
2answers
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.
0
votes
2answers
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 ...
4
votes
2answers
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 ...
0
votes
0answers
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 ...
7
votes
2answers
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 ...
8
votes
2answers
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 ...
4
votes
2answers
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 ...
3
votes
1answer
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 ...
0
votes
1answer
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 ...
7
votes
1answer
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 ...
6
votes
1answer
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 ...
1
vote
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.
6
votes
1answer
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 ...
3
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 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, ...
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
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 ...
0
votes
0answers
107 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\...
0
votes
0answers
119 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 $...
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 ...
19
votes
7answers
3k 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
41 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 $...
5
votes
1answer
238 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
90 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: ...
-2
votes
2answers
1k views

How to prove P ⊆ Co-NP

My approach Let L ∈ P $\exists$ Turing Machine $M_1$ which decides L. We can easily construct $M_2$ which decides $\bar{L}$ $\bar{L}$ ∈ CO-NP $\implies$ P ⊆ Co-NP I'm not sure ...
0
votes
0answers
54 views

If EXP = NEXP, can we say anything about P and NP? [duplicate]

I found one older question asked about this but without any responses.
4
votes
1answer
89 views

Logarithmic Randomness is Necessary for PCP Theorem

I am trying to proof the following statement: If $ {\rm SAT} \in {\rm PCP}[r(n),O(1)]$, where $ r(n)=o(\log n)$, then ${\sf P}={\sf NP}$. Here are my ideas for the proof: It can be easily worked ...
12
votes
2answers
5k 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 ...
-2
votes
1answer
98 views

Time Complexity and Optimization for the Algorithm?

I have found a algorithm to check whether a Hamiltonian Cycle Exists in the graph or not, but not able to compute/analyse it's time complexity. The algorithm is as follows : Label all the vertices ...
0
votes
1answer
84 views

Does classification of a problem also require the algorithm used? [duplicate]

Just learnt that a problem in computer science can be divided into the following categories Polynomial problems NP problems NP hard problems NP complete problems ...
2
votes
1answer
174 views

Schaefer's dichotomy theorem and reformulating 3-literal clauses

Does Schaefer's dichotomy theorem establish that a general 3-sat clause cannot be transformed into an equivalent set of 2-sat/Hornsat/affine clauses (using auxiliary variables) or just that this would ...
10
votes
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 ...
10
votes
3answers
4k 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. ...
1
vote
2answers
773 views

What is the evidence that P could equal NP?

What is the evidence that P could equal NP? I guess this is the same as asking: If it's known that $P \subseteq NP$ (depending on standard), then why is this not enough? Why assume that P could ...
3
votes
2answers
630 views

Is my theorem about $P \neq NP$ correct? [closed]

It is known that there are problems in P that, provably, are not solvable in less than $O(N^k)$, for some $k$. Now consider some infinite set $K \subseteq \mathbb{R}^+_0$ such as K is unbounded from ...
1
vote
2answers
2k views

If an NP-complete problem is shown to have a non-polynomial lower bound, would that prove that P != NP?

I understand that the Cook-Levin theorem proved that any NP problem is reducible to an NP-complete problem, which signifies that if a polynomial-time algorithm for an NP-complete problem is found, it ...
4
votes
1answer
97 views

Constructing languages in NPI other than through Ladner's Theorem

I have seen proofs of Ladner's theorem which detail the construction of languages in NPI assuming P $\neq$ NP. However, I was wondering if there are any other constructions using the fact that sparse ...
9
votes
0answers
275 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.\ \...
14
votes
1answer
2k views

Why do Shaefer's and Mahaney's Theorems not imply P = NP?

I'm sure someone has thought about this before or immediately dismissed it, but why does Schaefer's dichotomy theory along with Mahaney's theorem on sparse sets not imply P = NP ? Here's my ...
1
vote
0answers
54 views

NP-Hard vs NP-Complete Why NP-complete so important? [duplicate]

A problem $L$ is NP-complete when:- $L\in \text{NP}$ For every problem $L' \in \text{NP}$, $L'$ is polynomial time reducible to $L$ When at least property 2 is satisfied for a problem $L$ (but not ...