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 ...
27
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 ...
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 ...
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
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
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
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,5171 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
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
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
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 ...
9
Add $n-2k$ extra vertices, each connected to all the original vertices with zero-weight edges, and add a large enough number $W$ to each of the original edges to make their weights all positive. Then look for the minimum weight perfect matching.
9
As already noted in the comments, the question is based on a misunderstanding; the actual Positivstellensatz is a stronger statement than Artin’s theorem on nonnegative polynomials, and the real Nullstellensatz as stated in the question is indeed its special case.
Other comments asked for lecture notes with a proof of the Positivstellensatz, and as I do not ...
9
This problem is in P, it can be reduced to the Minimum cut problem.
The graph construction is as follows - Add a source and a sink vertex. For each vertex $i$, add an edge with cost $w(i)$ from source to $i$ and another edge of cost $s(i)$ from $i$ to sink. Also add edges from $i$ to $j$ of cost $t(i,j)$ for every pair of vertices $i$ and $j$.
The cost of ...
8
You could approach this with a "second moment method" calculation, similar to the one I used in A sharp threshold for a random constraint satisfaction problem, Discrete Mathematics 285/1-3 (2004), 301-305.
When the average degree grows like a sufficiently large constant times $\log n$, this approach has often been sufficient to find precisely the threshold ...
8
Well, here's a possible solution:
The reduction will be from 3SAT.
Input: $m$ DNF clauses $(\varphi_1,\ldots,\varphi_m)$ over $n$ variables $(x_1,\ldots,x_n)$.
Reduction:
Create a set of items composed of two items for every variable: $x_i, \overline x_i$, corresponding to a $True$ assignment to either the variable $x_i$ or its negation, plus one ...
Only top voted, non community-wiki answers of a minimum length are eligible
