Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [p-vs-np]

Questions about or related to P vs. NP

2
votes
1answer
274 views

Is there a counterexample to this work?

Is there a counterexample to this claim https://arxiv.org/abs/1610.00353? They claim a $O(n^6)$ LP model with simulations to support. I think asking validity is not a reasonable problem. However ...
5
votes
1answer
230 views

Is Murphy's Law of Complexity Theory consistent? What separations/collapses does it imply?

A decade ago I observed what I dub "Murphy's Law of Complexity Theory": whenever a new separation or collapse is discovered, the question is answered in the direction that makes $P\overset?=NP$ most ...
15
votes
1answer
1k views

Algorithm whose running time depends on P vs. NP

Is there a known, explicit example of an algorithm with the property such that if $P\neq NP$ then this algorithm doesn't run in polynomial time and if $P=NP$ then it does run in polynomial time?
15
votes
1answer
563 views

Barriers to show $P=NP$

We all know showing $P\ne NP$ has barriers. We all have studied these barriers because we believe $P\ne NP$. However assume $P=NP$ and there are wise people who believe that possibility exists. If ...
2
votes
1answer
183 views

P vs. NP in a logic with a random oracle

Choose a random oracle $f : \{0,1\}^\ast \to \{0,1\}$, and define the logic $ZFC^f$ by adding a fresh symbol $g$, an axiom that $g$ has the correct type, and one axiom $g(s) = f(s)$ for each $s \in \{...
2
votes
0answers
118 views

What are some known methods for showing that a class has no complete problems?

The only way that I know of is the way that you can show that $RE \cap coRE$ does not via diagonalization. Mostly curious because if $NP \cap coNP$ has no complete problems then $P \neq NP$. I tried ...
-3
votes
1answer
111 views

What is wrong with this procedure to convert quadratic programming to convex quadratic programming?

Consider the feasibility quadratic program with constraint $$\sum_{i=1}^nc_{i1}x_{i}\leq \ell_1$$ $$\vdots$$ $$\sum_{i=1}^nc_{it}x_{i}\leq \ell_t$$ $$\sum_{i,j=1}^na_{ij}x_{i}x_{j}+\sum_{i=1}^nb_{i}x_{...
3
votes
0answers
205 views

Is there any known strategy that avoids circuits and that respects believed separations to prove $P$ is not $NP$?

Vinay Deolalikar's approach tried to randomness is not strong enough, Blum's proof tried to show $P/poly$ is not strong enough, Mulmuley's and Smale's approach (while not enough to show $P\neq NP$) ...
0
votes
1answer
218 views

${\bf NP} \not = {\bf E}$ and ${\bf PSPACE} \not = {\bf E}$

We know that ${\bf NP} \subseteq {\bf PH} \subseteq {\bf PSPACE}$. We also know that ${\bf E} \subset {\bf EXP}$, where ${\bf E} = \cup_c DTIME[2^{cn}]$ and ${\bf EXP} = \cup_c DTIME[2^{n^c}]$. It ...
2
votes
1answer
471 views

Can one prove the discovery of a P versus NP solution without actually revealing it?

Suppose a person has proved that P≠NP. He wants to let the world know that he has solved the P versus NP problem but does not want to reveal that he has proved P≠NP as opposed to P=NP. Is there any ...
1
vote
1answer
125 views

Unambiguous SAT and sparse languages

What is the consequence if there are only polynomially many 'yes' classes of instances of a language that is polynomial time reducible from a problem equivalent to UnambiguousSAT (such as possibly ...
5
votes
0answers
158 views

Converse to natural proofs theorem?

Natural proofs paper shows 'if there is a natural property not possessed by any function in P/poly then there is no $2^{n^\epsilon}$-hard PRG'. Is it easy to see the converse 'if there is no $2^{n^\...
6
votes
2answers
226 views

ETH-Hardness of $Gap\text-MAX\text-3SAT_{c}$

The PCP theorem can be stated like this : There is a polynomial time reduction from SAT to $Gap\text-MAX\text-3SAT_{c}$ i.e. there is a reduction that maps an instance $\phi$ of SAT to an instance $...
12
votes
3answers
817 views

Why do computer scientists on the whole work under the assumption that P ≠ NP?

Coming from a math background, it seems interesting to me that on the whole computer scientists tend to work under the assumption that $P \neq NP$. While there is no proof either way, generally, ...
17
votes
0answers
191 views

What is the background in algebraic geometry and representation theory needed for geometric complexity theory? [duplicate]

I'm a mathematics student in my junior year and I'm interested in computational complexity and specially geometric complexity theory. I'm going to learn algebraic geometry and representation theory ...
8
votes
0answers
183 views

What would be the consequences if all _infinite_ NP-complete languages are p-isomorphic?

The famous Isomorphism Conjecture of Berman and Hartmanis says that all $NP$-complete languages are polynomial time isomorphic ($p$-isomorphic) to each other. It has been an early attempt (published ...
2
votes
0answers
111 views

What would faster Fourier Transform(FFT?) and/or multiplication algorithms imply?

There are many problems which have implications on P vs. NP and other complexity classes. Supposing that we're interested in Fourier transforms and/or multiplication algorithms, do faster Fourier ...
7
votes
1answer
419 views

Is “two or zero” matching in a bipartite graph NP complete?

I have this problem, which I haven't seen before in the literature: given a bipartite graph and a natural number $k$, can we select at least $k$ of the edges such that each left-hand vertex is ...
7
votes
1answer
242 views

Two DFA intersection emptiness connections to SETH & L vs P

(re "fine grained complexity") Wehar has proved that Two DFA intersection emptiness in $O(n^{2-\epsilon})$ time → SETH false. does anyone see any particular key proof difficulty, challenge, ...
17
votes
4answers
2k views

Chaos and the $P{=}NP$ question

I am interested in learning connections between "chaos," or more broadly, dynamical systems, and the $P{=}NP$ question. Here is an example of the type of literature I am seeking: Ercsey-Ravasz, ...
0
votes
0answers
137 views

Consequences of VP = VNP on randomness

According to the answers in posting it is possible that $\mathsf{VP} = \mathsf{VNP}$ and $\mathsf{P} \neq \mathsf{NP}$ are simultaneously correct. $\mathsf{VP} = \mathsf{VNP}$ implies $\mathsf{P/...
-2
votes
1answer
327 views

What is the status of intermediate problems if P is not NP in worst way imaginable?

Assume $P\neq BPP\neq NP$ with caveat that there is a deterministic algorithm for every $NP$ complete problem with input size $n$ bits in $2^{(\log n)^{1+f(n)}}$ arithmetic operations on $\log n$ ...
4
votes
1answer
208 views

Implications of $\mathsf{P}\neq\mathsf{NP}$ in $\mathsf{BSS}$ model

What are implications of $\mathsf{P}\neq\mathsf{NP}$ in $\mathsf{BSS}$ model to $\mathsf{Turing}$ model and $\mathsf{Valiant's}$ counting complexity model? In opposite direction what are implications ...
12
votes
1answer
467 views

L/P/PSpace vs P/NP

in 1979 Hopcroft/ Ullman wrote that L ⊆ P ⊆ NP ⊆ PSpace is known but L ⊊ PSpace is the only proper (& trivial) containment known although all are conjectured to be proper containments, and "where ...
-2
votes
1answer
106 views

what can be said about complexity of “typical” supercomputing programs/ applications? any NP hard?

supercomputers have risen dramatically in their computational powers last few decades due to Moore's law & also increasing parallelism technology in hardware and software. many different types of ...
4
votes
1answer
342 views

Analogies between VNP and NP

Valiant introduced the class VNP with respect to "arithmetic circuits" over 35 years ago in a "rough" analogy to NP. Recently, there have been major advances in the area of arithmetic circuits eg as ...
1
vote
0answers
232 views

What's the Impact if proven NP/co-NP=PSPACE on settling P=NP? The future directions it opens to settle/attack P=NP? Remaining classes left outside?

The primary Impact i know would be that: Polynomial Hierarchy collapses to Level 1. NP=co-NP NP=BPP NP=PSPACE BQP=NP and so on.. What are the attack directions it will open for settling P=NP (in ...
0
votes
1answer
378 views

Is where an oracle B in EXP that $P^B$ $ \ne$ $NP^B$? [duplicate]

According to Baker, Gill, Solovey where is an oracle A in EXP, so $P^A$ = $NP^A$. But is there an oracle B in EXP, what $P^B$ $\ne$ $NP^B$?
1
vote
0answers
241 views

intuition that VP=?VNP is (not?) connected to P=?NP

recently there has been major progress into the VP=?VNP problem for algebraic circuits originated by Valiant, inspiring some optimistic outlook on its eventual or imminent resolution.[1] what is an ...
12
votes
2answers
477 views

Looking for Literature Source for Following idea

I am quite certain that I am not the first to entertain the idea that I am going to present. However, it would be helpful if I can find any literature related to the idea. The idea is to construct a ...
22
votes
6answers
2k views

Statements that imply $\mathbf{P}\neq \mathbf{NP}$

This is sort of an open-ended question - for which I apologize in advance. Are there examples of statements that (seemingly) don't have anything to do with complexity or Turing machines but the ...
1
vote
0answers
136 views

What is known about lower bounds on the algorithm if P=NP

I recall Scott Aaronson making the claim that either $P\neq NP$ or he has superpowers. What reason is there, if any, to believe that it is not the case that any decision procedure has constants (or ...
9
votes
0answers
476 views

Assigning probability to membership in an NP-complete language

Motivation Assuming $\mathsf{P}\ne\mathsf{NP}$, it is impossible to efficiently decide membership in an NP-complete language. I would like to assign probability to such membership, in some sense. ...
7
votes
2answers
605 views

Baker Gill Solovay $P^B \ne NP^B$ relativization, what class is $B$ in?

A recent question asks whether relativization is well-defined. This question wonders how to put one use of it on firmer ground. In the BGS 1975 proof that there exists a language $B$ such that $...
3
votes
0answers
242 views

Does $P\neq NP$ imply any larger separation?

I've asked a similar question in cs.se, but didn't get a satisfying answer. Assuming $P\neq NP$, what can we say about the runtime of any algorithm for an $NP$-complete problem? Obviously, it means $...
0
votes
1answer
135 views

Assume that $\mathsf{NP} \subseteq \mathsf{P}/\text{log(n)}$, does it imply that $\mathsf{P} = \mathsf{NP}$? [closed]

I am trying to either prove or refute the claim mentioned in the title. Any ideas ?
5
votes
3answers
669 views

If SAT is in PCP, for some constant q, then P = NP

I have seen this statement before, but I haven't really seen a proof of it: If $SAT\in PCP_{1,2^{−q}}[\log(n),q]$, for some constant $q$, then $P = NP$. Now, if $SAT\in PCP_{1,2^{−q}}[\log(n),q]$, ...
1
vote
1answer
431 views

equivalent way(s) of expressing P=?NP problem in linear programming?

the paper "In defense of the Simplex Algorithm's worst-case behavior" Disser/Skutella [1] was recently cited on this tcs.se site by saeed on another interesting question. the paper introduces the idea ...
6
votes
2answers
298 views

NPI-candidate hereditary graph property?

A graph property is called hereditary if it is closed with respect to deleting vertices. There are many interesting hereditary graph properties. Moreover, a number of nontrivial general facts are ...
18
votes
1answer
419 views

Natural candidate against the Isomorphism Conjecture?

The famous Isomorphism Conjecture of Berman and Hartmanis says that all $NP$-complete languages are polynomial time isomorphic (p-isomorphic) to each other. The key significance of the conjecture is ...
-5
votes
1answer
218 views

Can on every instance P = NP? [closed]

I want to ask a question concerning some aspects of the P vs. NP problem. NOTE: Possibly by "popular" standards i am a crank (i tend towards P=NP), but lets focus on the issue (please with a grain of ...
27
votes
6answers
1k views

Why are so few natural candidates for NP-intermediate status?

It is well known by Ladner's Theorem that if ${\mathsf P}\neq \mathsf {NP}$, then there exist infinitely many $\mathsf {NP}$-intermediate ($\mathsf{NPI}$) problems. There are also natural candidates ...
12
votes
3answers
710 views

What are natural examples of non-relativizable proofs?

As I understand it, a proof that P=NP or P≠NP would need to be non-relativizable (as in recursion theory oracles). Virtually all proofs seem to be relativizable, though. What are good examples of ...
7
votes
1answer
527 views

Public-key encryption without the assumption that $P \neq NP$

I'm not talking about the RSA, El-gamal, nor any specific encryption scheme. Rather, my question, as related to this and this threads, is why the idea of Public-Key encryption scheme cannot be secure ...
16
votes
1answer
698 views

Gowers “discretized Borel determinacy” approach

Gowers has recently outlined a problem, which he calls "discretized Borel determinacy," whose solution is related to proving circuit lower bounds. Can you provide a summary of the approach that is ...
4
votes
2answers
411 views

P/poly vs NP separation based on circuit trees instead of DAGs

there are various theorems that relate major complexity class separations to circuit family DAGs sizes, in particular for P/poly vs NP. in contrast, are there theorems/conjectures that relate P/...
11
votes
2answers
1k views

On the provability of P versus NP

First of all, my understanding on Gödel's incompleteness theorem (and formal logic in general) is very naive, also is my knowledge on theoretical computer science (meaning only one graduate course ...
9
votes
3answers
678 views

Could there be an extremely large hidden subset of Polynomially solvable problems within NP-Complete problems?

Suppose P != NP. We know that we can make easy instances of 3-SAT at any time. We can also generate what we believe to be hard instances (because our algorithms can't solve them quickly). Is there ...
25
votes
4answers
1k views

Best known deterministic time complexity lower bound for a natural problem in NP

This answer to Major unsolved problems in theoretical computer science? question states that it is open if a particular problem in NP requires $\Omega(n^2)$ time. Looking at the comments under answer ...
8
votes
3answers
1k views

P vs NP: Instructive example of when Brute Force search can be avoided

To be able to explain the P vs NP problem to non-mathematicians I would like to have a pedagogical example of when Brute Force-search can be avoided. The problem should ideally be immediately ...