17

There is the descriptive complexity formulation:
P = NP is equivalent to the statement that every property expressible by a second order existential statement is also expressible in first order logic with a least fixed point operator.
See, e.g., Immerman's survey here: https://people.cs.umass.edu/~immerman/pub/capture.pdf

14

You don't need an anchor tile. Jed Yang and I recently solved this on the way to stronger NP-completeness results (versions of this result were already known). We explain it all here. Similarly, the rectangular tileability problem is undecidable according to Yang's recent result here.

13

For what it’s worth, Fortnow and Rogers constructed an oracle relative to which P = BQP, but the polynomial hierarchy does not collapse (hence in particular P ≠ NP).

answered Aug 9 '14 at 20:12

Emil Jeřábek

36.4k33 gold badges115115 silver badges174174 bronze badges

12

If, for some (mysterious) reason, injective reductions were taken as the standard, then, even if we couldn't reduce SAT to certain PTime problems by such restricted reductions, that wouldn't tell us that SAT can't be solved in PTime.
In other words, the fact that any PTime solvable problem can be reduced to any other (nontrivial) PTime solvable problem is ...

answered Sep 30 '16 at 23:35

Andreas Blass

67.1k88 gold badges167167 silver badges264264 bronze badges

11

I tried to give a formal proof of the NP-completeness of the problem.
For the reduction details see my answer on cstheory.stackexchange.com

11

If one considers the anchor-tile tiling problem, where the tiling must include a specified anchor tile, then indeed this problem is NP-complete. To see this, suppose that we have a given NP problem, where there is a polynomial time computable Turing machine $M$, such that we want to know on input $x$ whether there is some $y$ such that $M$ accepts $(x,y)$, ...

answered Feb 16 '14 at 4:42

Joel David Hamkins

189k3232 gold badges579579 silver badges10201020 bronze badges

10

Yes, this problem is NP-hard. Before we start, notice that it doesn't matter that we want a majority, instead the desired number of districts could be a part of the input. This is because somewhere neatly separated from the rest of the square/rectangle we could place many voters for ourselves with which we can claim any fixed amount of districts. Therefore, ...

9

The general case of the domination number problem reduces to the non-bipartite case. Given a (possibly bipartite graph) $G$, create new graph $G'$ consisting of an copy of $G$ and a disjoint copy of $K_3$. The domination number of the new (non-bipartite) graph $G'$ is exactly one more than that of the original graph $G$. So computing the domination number of ...

answered Mar 5 '14 at 16:20

9

The tensor product has a way of making easy problems into (NP-)hard problems. Rank of a 2-tensor (matrix)? Easy. Rank of a 3-tensor? NP-hard. Spectral norm of a matrix? Easy. Spectral norm of a 3-tensor? NP-hard. Etc. There is a nice article by Hillar and Lim about this.
As a direct corollary of the above fact, many natural linear algebra problems that come ...

9

This 2003 paper shows there has been quite a bit of work. The focus is on
"fast" exponential-time solutions to NP-hard problems, including the TSP,
SAT, knapsack problems, graph coloring, to mention a few:
Woeginger, Gerhard J. "Exact algorithms for NP-hard problems: A survey." Combinatorial Optimization—Eureka, You Shrink!. Springer Berlin Heidelberg, ...

answered Sep 1 '16 at 11:48

Joseph O'Rourke

140k2626 gold badges295295 silver badges834834 bronze badges

9

The closest thing to what you're looking for may be the work of Adam Yedidia and Scott Aaronson, who have, for example, constructed an explicit 5372-state Turing machine that halts if and only if the Riemann Hypothesis is false.
This doesn't quite satisfy your requirements because Yedidia and Aaronson were interested in the halting problem rather than SAT, ...

answered Dec 28 '17 at 1:20

Timothy Chow

57.6k1919 gold badges256256 silver badges439439 bronze badges

9

Apparently, we would have gotten at least half of the BGS result without any of the three named authors and also without any of the 4 people they credit, all we needed was Dekhtiar. 😊
The Annals of the History of Computing (1984) has a historical account by Trakhtenbrot of the proof by Dekhtiar (1969) that we can have $P^A\ne NP^A$.
Trakhtenbrot also ...

answered Aug 20 '20 at 7:02

Bjørn Kjos-Hanssen

23k33 gold badges4747 silver badges106106 bronze badges

8

No.
The statement "P=BQP" means that a quantum computer can be simulated efficiently (in polynomial time) on a classical computer. Since a quantum computer cannot solve NP-complete problems efficiently (at least not as far as we know), neither will a classical computer, so P=BQP will not help.

answered Aug 9 '14 at 20:09

Carlo Beenakker

130k1212 gold badges318318 silver badges456456 bronze badges

8

By knot, I assume you mean a knot in $S^3$. Typically a knot is encoded as a diagram, which you might think of as a tetravalent planar graph, with some kind of description of undercrossings and overcrossings, say by some kind of labelling of the half edges incident to every vertex. Abstractly, the notion of equivalence is ambient isotopy; combinatorially, ...

8

Here is a simple embedding of 3-SAT into the current setup (the question is just if we can get all vectors good).
Call the first column special with $1$'s.
Split the other variables into pairs $(a,b)\in\{(0,0),(1,1),(1,0),(0,1)\}$.
Our first task will be to eliminate any $(1,0)$ or $(0,1)$ options. For that,
use the Hadamard matrix without the ...

7

This 2012 report of "A fast branching algorithm for unknot recognition with experimental polynomial time behaviour" by B. Burton and M. Ozlen may well represent the current status of the problem:
It is a major unsolved problem as to whether unknot recognition - that is, testing whether a given closed loop in $R^3$ can be untangled to form a plain circle - ...

answered Dec 7 '16 at 16:56

Carlo Beenakker

130k1212 gold badges318318 silver badges456456 bronze badges

7

Recently, Marc Lackenby discussed a new algorithm for unknot recognition in a talk at the Newton Institute (see time around 1:03). He conjectures (but indicates at the time that it is work-in-progress) that his algorithm runs in quasi-polynomial time ($c^{\log c}$, where $c$ is the crossing number). In any case, his talk discusses the state of the art of the ...

6

This seems to be polynomial. Here is a proof. It will be convenient to regard $A$ as an edge-weighted complete bipartite graph $G$. Let $m_1 < \dots < m_\ell$ be the list of edge weights of $G$, let $E_i$ be the set of edges of weight $m_i$, and let $G_i:=G \setminus (E_1 \cup \dots \cup E_i)$. Now test if $G_1$ has a perfect matching (note this ...

6

It's NP-complete (even for 0-1 weights) by a reduction from feedback arc set in directed graphs. Let D be a digraph in which you want to compute a feedback arc set, A be the vertices of D, B be the edges of D, and E be the vertex-edge incidence relation of D. Assign a weight 1 for ab when a is the incoming endpoint of b, and 0 when it is the outgoing ...

answered Sep 3 '14 at 16:11

David Eppstein

17.9k22 gold badges4949 silver badges117117 bronze badges

6

The problem is also trivially NP-complete without an anchor tile. The trick is that we can easily force any tile to become an anchor tile. First, take a set of tiles that have a unique way of tiling an $n\times n$ square, e.g., by putting (respectively matching) $(i,j)$'s on their sides where $1\le i,j\le n$. Then take the "direct product" of this tile set ...

6

Here is one such result.
Stephen A. Vavasis.
"On the complexity of nonnegative matrix factorization."
2007. (arXiv abstract link)
"In this report, we define an exact version of NMF [nonnegative matrix factorization]. Then we establish several results about exact NMF: (1) that it is equivalent to a problem in polyhedral combinatorics; (2) that it ...

6

For Boolean Satisfiability (SAT), there is Sat Competition: http://www.satcompetition.org/
State of the art SAT solvers often perform very efficiently, far faster than exponential. At the above link there should be results to see how large instances were solved.
Sucess story: Using SAT solver, important partial results about a conjecture of Erdos were ...

6

I think "Geometric Complexity Theory" is roughly speaking an attempt to do what you're talking about: formulate P vs. NP in very different language. See https://en.wikipedia.org/wiki/Geometric_complexity_theory. I think that technically it may be dealing with "VP vs. VNP" rather than "P vs. NP" but in spirit it fits your request.

6

If I understand the question, then the triple $(30,840,3)$ could come from $6+10+14=30$, $6\times10\times14=840$ or from $7+8+15=30$, $7\times8\times15=840$.

6

No, the solution is not always unique. You may be interested in a well-known recreational math puzzle in which, essentially, one needs to find the values of $S$ for which $\langle S, 72, 3\rangle$ does not have a unique solution: https://en.wikipedia.org/wiki/Ages_of_Three_Children_puzzle . I do not write the counterexample here to avoid spoiling the puzzle, ...

5

(This isn't an answer, but I'm not allowed to comment yet and I think this is a worthwhile question, even if it means violating the rules; i'll delete the post when the time comes)
You claim that usual matrix norms do not work because of the $|f(x_1)-f(x_2)|$ criterion, but if $f$ is differentiable, then given any $x_1$ it is Lipschitz in some neighborhood ...

5

This paper by Karabayashi and Reed seems to be closely related to what you are looking for.

answered Jul 28 '13 at 18:37

Igor Rivin

92.5k1111 gold badges131131 silver badges329329 bronze badges

5

You may want to look at the work of Arora, Barak, Ragavendra, Steurer etc relating details of graph spectra to expansion of small sets and to the Unique Games Conjecture. Sample references are:
Ragavendra–Steurer, Ragavendra–Steurer–Tetali,Arora–Barak–Steurer.

5

I seem to have a polynomial-time algorithm that untangles the unknot. But I suspect that hubris lurks around every corner in this game.
I'm pretty sure I can show that the algorithm runs in polynomial-time. But I now realise that I don't know if it is always able to simplify every tangle.
As always, the trick is to find a representation that makes it ...

5

This is somewhat complementary to domotorp's existing answer, explaining the first paragraph in more detail.
Let's consider the tightest possible case, where $n = 2m - 1$ and there are $m^2$ A-squares and $n^2 - m^2$ B-squares. The problem is to partition the $n \times n$ grid into $n$ polyominoes of $n$ squares each, such that $m$ of the polyominoes each ...

Only top voted, non community-wiki answers of a minimum length are eligible

#### Related Tags

np × 103computational-complexity × 64

algorithms × 21

graph-theory × 20

co.combinatorics × 13

computer-science × 11

computability-theory × 8

combinatorial-optimization × 7

reference-request × 5

lo.logic × 4

lattices × 4

graph-colorings × 4

open-problems × 4

approximation-algorithms × 4

linear-algebra × 3

coding-theory × 3

sat × 3

discrete-geometry × 2

oc.optimization-and-control × 2

big-list × 2

knot-theory × 2

linear-programming × 2

permutations × 2

quantum-mechanics × 2

proof-theory × 2