Share Your Experience: Take the 2024 Developer Survey

# Questions tagged [p-vs-np]

Questions about or related to P vs. NP

92 questions
Filter by
Sorted by
Tagged with
101 views

### Can you find a counterexample / disprove my P=NP solution?

I've posted the full article here. The source code is available here. Basically, in the Linear Programming (LP) task, we solve a system of inequalities: one inequality per BSAT clause. In each ...
250 views

### What is the 'P=NP?' building?

I remember that I read somewhere some years ago that they've built a computing building with the 'P=NP?' question built in it from bricks so that they later have the option to rearrange these bricks ...
• 14k
197 views

### Bottom up TSP solution?

I'm not sure if this is something new or if I'm just not getting previous efforts. TSP can be thought of as a list of weighted links and nodes. If one takes the Nearest Neighbor (NN) of every node and ...
207 views

### Complexity of solving a higher-order degree polynomial equation? P-problem or NP-problem or neither?

I am a mathematician and I am very new to theoretical computer science. The definition of P/NP problem I found in wiki is that: P is the set of decision problems solvable in polynomial time by a ...
1k views

### Formulating P vs NP without Turing machines

Computability in terms of Turing machines is equivalent to computability described by computable functions (based on primitive recursive functions, introducing the $\mu$-operator and so on). Is there ...
1 vote
78 views

### Consequences of a $Parity$ $P$-problem being reducible to a sparse language?

$Parity$ $P$ is the class where an $NP$-machine answers $YES$ if and only if the number of accepting paths of that turing machine is odd. With regards to the $P$ vs $NP$ question, there is a theorem ...
1 vote
478 views

### Is it known that P $\neq$ NP implies BQP $\neq$ NP?

Pretty much the title. Is there any result that shows that $P \neq NP \Rightarrow BQP \neq NP$. I think it's pretty clear that $BQP \neq NP \Rightarrow P \neq NP$, as $P$ is a subclass of $BQP$. But ...
• 111
1 vote
1k views

### Did Jinliang Wang solve the P versus NP problem?

Recently, I saw a paper on the Internet [1]. Did the author of this paper, Jinliang Wang, solve the P versus NP problem? Reference [1] Wang, J. L. (2018) Fast Algorithm for the Travelling Salesman ...
100 views

### Why if non determinism adds no power at all to DFAs or to Turing machines, why is it that most people beleieve P != NP [closed]

During Theory of Computation or Automata Theory or the equivalent class at my University, I was shown that non deterministic and deterministic automata can solve the exact same set of problems, then ...
1 vote
266 views

### What if NP = coNP?

Are there any major implications of NP = coNP (if true) the way there would be if P=NP? I'm thinking of real-world implications analogous to the encryption-pocalypse (excuse the drama) that would ...
• 33
74 views

### Number of outputs produced by levin search variant (SIMPLE)

Let $f$ be an inverting problem. If there is an algorithm A that invert $f$ in time $t(n)$, then the SIMPLE algorithm below invert $f$ in time $c.t(n)$ where $c$ is a constant depending only on $A$ ...
1 vote
156 views

• 3,263
125 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 ...
• 1,572
126 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_{...
• 12.9k
224 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$) ...
• 12.9k
373 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 ...
556 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
230 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 ...
• 12.9k
183 views

• 243
1k 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, ...
• 273
224 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 ...
• 269
362 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 ...
• 11.4k
133 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 ...
• 2,100
737 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 ...
328 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, ...
• 11k
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, ...
• 3,753
1 vote