41
An example that I love is the problem where, given distinct $a_1, a_2, \ldots, a_n \in \mathbb{N}$, decide if: $$\int_{-\pi}^{\pi} \cos(a_1 z) \cos(a_2 z) \ldots \cos(a_n z) \, dz \ne 0$$
This at first seems like a continuous problem to evaluate this integral, however it is easy to show that this integral is not zero iff there exists a balanced partition of ...
26
There are many continuous problems of the form "test whether this combinatorial input can be realized as a geometric structure" that are complete for the existential theory of the reals, a continuous analogue of NP. In particular, this implies that these problems are NP-hard rather than polynomially solvable. Examples include testing whether a given graph is ...
25
This is really a stubborn -- and well-studied -- problem. Regarding positive results, an exact algorithm by Kameda and Weiner, a heuristic approach by Polák, and a recent approach using SAT solvers by Geldenhuys et al. come to mind. But there seem to be far more negative results ruling out other possible approaches (e.g. approximation algorithms, special ...
22
In some technical sense you are asking whether $P = NP \cap coNP$. Suppose that $L \in NP \cap coNP$, thus there exists poly-time $F$ and $G$ so that $x \in L$ iff $\exists y: F(x,y)$ and $x \not\in L$ iff $\exists y: G(x,y)$. This can be recast as a minmax characterization by
$f_x(y) = 1$ if $F(x,y)$ and $f_x(y) = 0$ otherwise; $g_x(y) = 0$ if $G(x,y)$ ...
15
Here is an example, where one can produce a solution in polynomial time, but evaluating a given solution is NP-hard.
Input: Positive integers $n,k$ (in unary encoding), with $k\leq n$.
Task: Maximize the number of edges in an $n$-vertex graph under the constraint that its maximum clique size is at most $k$.
Solution: It is known from extremal graph ...
14
Look for Minimum Rainbow Subgraph.
14
Seymour and Thomas showed a min-max characterization of treewidth. Yet, tree width is NP-hard. This however is not quite the kind of characterization you are asking for, because the dual function $g$ is not a polynomial time computable function of a short certificate. This is most likely unavoidable for NP complete problems, because otherwise we would have ...
13
Parity games, Mean-payoff games, Discounted games, and Simple Stochastic games fall within this category.
All of them are infinite two-player zero-sum games played on graphs, where players control vertices and choose where a token should go next. All have equilibria in memoryless positional strategies, meaning that each player chooses an edge at each choice ...
13
While this doesn't exactly answer your original question, it's a (conjectural) example of a sort of philosophical counterpoint: a problem where the presentation is discrete but all of the hardness comes from the 'continuous' aspect of the problem.
The problem is the Sum of Square Roots problem: given two sets of integers $A=\{a_1, a_2, \ldots, a_m\}$ and $B=...
12
Sorry I'm late! In quantum computing theory, there are lots of examples of optimization problems over the unitary group that, surprisingly (at least to me), are solvable in (classical) polynomial time by reduction to semidefinite programming.
Here was an early example: solving a problem of mine from 2000, in 2003 Barnum, Saks, and Szegedy showed that Q(f), ...
12
The premise of the question is a little flawed: there are many who would argue that quadratics are the real "boundary" for tractability and modelling, since least-squares problems are almost as 'easy' as linear problems. There are others who'd argue that convexity (or even submodularity in certain cases) is the boundary for tractability.
Perhaps what is ...
12
An optimal solution lies on some face. So, we can go through all the faces of the cube, and find all stationary points on each of the faces.
Here is a more concrete procedure. A face of the cube can be characterized by two disjoint index sets $I_0$ and $I_1$. For $i \in I_0$, we fix $x_i = 0$, and for $i \in I_1$ we fix $x_i = 1$. Let $\tilde{x}$ ...
11
This is called the (linear) assignment problem. It can be solved efficiently through linear programming over the Birkhoff polytope.
11
I meant to leave this as a comment, but I don't have the reputation to do so yet. This question was crossposted over at Mathoverflow, where I mention that the problem is NP-complete.
See here.
To avoid a contradiction with Chandra Chekuri's answer, I do not believe that the LP given in his answer is integral. To see this consider the uniform matroids $...
11
Your problem (as stated) seems to be NP-hard. Here is a reduction from Partition.
Given an instance of Partition (a collection $x_1,\ldots,x_n$ of positive integers), construct a graph with $n+1$ vertices $v_1,\ldots,v_{n+1}$ and, for each $i$, two edges from $v_i$ to $v_{i+1}$: one of cost zero, one of cost $x_i$.
Suppose the Partition instance is ...
11
(Moved from comments) Here's an idea for getting a constant factor approximation, assuming P and Q satisfy the triangle inequality. I thought it might give a 2-approximation, but all I can prove right now is an approximation ratio of 4.
(1) In the problem as stated, the weight of edge $pq$ in the combined graph (after the correspondence $p$–$p'$ and $q$–$q'$...
10
The problem is still NP-complete. Here's a reduction from the Treewidth problem on general graphs. Recall that for a graph G of treewidth at least two, the treewidth is not affected when subdividing an edge by a degree-2 vertex (i.e. replacing an edge $\{u,v\}$ by a new vertex $x$ and edges $\{u,x\}$, $\{x,v\}$ ).
Given an input graph $G$ on $n$ vertices, ...
10
In the geometric setting, where $C(x,y) = \|x - y \|$, this formulation is called the bottleneck matching problem. It's possible that this is the generic term for it (I've seen this formulation used in the Kleinberg-Tardos algorithms book for MSTs).
10
We did some research on the problem of proving in tree-like Resolution whether a fixed graph $G$ has a clique of size $k$ (where $k$ is usually small). In particular we discovered that refutations of size $n^{\Omega(k)}$ are needed for a large class of graphs.
You can find the paper Parameterized Complexity of DPLL Search Procedures at this link.
10
The problem is likely to be hard to approximate. The densest bipartite subgraph problem can be cast as a special case. Given a bipartite graph $(V,E)$ where $V=V_1 \uplus V_2$ define $f(S,T)$ for $S \subseteq V_1, T \subseteq V_2$ to be the number of edges between $S$ and $T$. Then $f$ satisfies the desired property. In fact $f(S,\cdot)$ is modular and so is ...
10
We can compute $m$ in linear time.
For simplicity suppose that the arrays are 0 based: $A[0..n-1]$, $B[0..n-1]$.
We want to compute $m = \max_i B[i]+i$.
Let $max = \max_i A[i]$.
Obviously $max \leq m$.
Let $A[j]$ be $B[k]$ after sorting. If $A[j] \leq max - n$ we have
$$B[k] + k \leq B[k] + (n-1) = A[j] + (n-1) \leq (max-n) + (n-1) = max-1 < max \leq ...
10
There is a naive algorithm for programs with bounded-size inputs: enumerate all programs in order of increasing length (or execution time, which is a bounded function of the length). If you can prove that the program is equivalent to the original, stop; otherwise keep searching.
This algorithm is sound. In order for it to be complete, you need to be able to ...
answered Mar 11 '14 at 11:24
Gilles 'SO- stop being evil'
2,4971 gold badge23 silver badges33 bronze badges
10
I would rephrase the question as follows:
Consider the function $F$ and the family of functions $F_{a,b}$ defined as
$$F_{a,b}(x) = F(a,b,x) =ax+b.$$
Can we compute $F_{a,b}$ faster than the complexity of $F$?
If yes, given $a$ and $b$, can we algorithmically find such an algorithm?
As babou wrote I think the answer depends on your computation ...
10
Fixed Point Logic $+$ Counting (FPC) is believed to capture most of the $P$ solvable problems. Anderson, Dawar and Holm 2015 [1]showed that optimization of linear programs is expressible in FPC. Dawar and Wang 2016 [2]showed that The FPC implementation of the ellipsoid method extends to semidefinite programs (subject to some technical conditions).
9
There's a simple reduction from knapsack. Binary search for the solution to your knapsack instance, then solve the "dual knapsack" with that value as your covering constraint $B$. Compare the value given by the "dual knapsack" against your knapsack packing constraint, which gives you the direction to continue the binary search.
I think you can use the same ...
9
So you are given a weighted undirected graph $G$. You want to find a shortest walk from $s$ to $t$ such that you visit all the vertices of the set $S$. You may choose to visit vertices in $V \setminus S$. You may visit vertices multiple times. You may use the edges multiple times. Let's call this problem $stSWALK$.
$stSWALK$ is equivalent to metric ...
9
Are you aware of the work on positive LPs/SDPs? There are a bunch of results in the area, mostly along the lines of "if the constraints of the LP/SDP are positive, then the problem can be solved in NC."
Some important references in this line of work are Luby-Nisan 93 and Jain-Yao 11. Another excellent resource is this slide of Rahul Jain's talk at the "...
9
How can this system be solved without using linear programming?
It cannot.
Your problem is the linear feasibility problem in the standard form, with an extra condition that the constraint matrix is sparse. Now note:
(1) It is well-known that linear programming is equivalent to the linear feasibility problem in the standard form.
(2) You can easily ...
9
OK. The DP algorithm seems to be unnecessarily complicated. After reading comments I think this might solve the Monotonic version of the problem (but I have not checked every detail).
First, assume each $x_i = \lfloor x_i\rfloor +\{x_i\}$, where $\lfloor x_i\rfloor$ is the integral part, $\{x_i\}$ is the fractional part. Assume $x_i$ is rounded to $\lfloor ...
9
A first observation is that the stochastic version of an optimization problem will always be at least as hard as the deterministic version, since fixed constant values in an optimization instance are degenerate special cases of random-variable values.
Now to understand the computational complexity of stochastic optimization problems in more detail, it's ...
Only top voted, non community-wiki answers of a minimum length are eligible
