42
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 ...
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
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
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'$...
11
The problem is very similar to Min Uncut. In Min Uncut, given a graph $G = (V, E)$, we need to find a subset of edges $E'$ s.t. $G - E'$ is bipartite; the objective is to minimize the size of $|E'|$. For brevity, let me call you problem $\cal P$ and Min Uncut $\cal U$.
Observation. An instance $G$ of $\cal P$ has a solution of cost 0 if and only if $G$ 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,5871 gold badge24 silver badges35 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 ...
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
For total cost, see http://en.wikipedia.org/wiki/Route_inspection_problem (also called the Chinese postman problem). The optimal solutions to this problem visit each edge at most twice, so they also optimize your width cost.
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 ...
8
Mainly, there exist 3 benchmarks to test shop scheduling problems.
Namely they are Taillard, Structured and ORLib benchmarks. These benchmarks have different
goals. The Taillard benchmark is the most
used benchmark in the literature. The benchmark targets permutation flowshop, flowshop, open shop and job shop scheduling problems. For details and download of ...
8
I think the answer to your question is dependent on the exact setting
of your problem, and in particular the representations you intend to
use for $a$, $b$, and $x$, as well as the available elementary
operations on these representations.
What you want to consider is a partial evaluation of the expression
$ax+b$ when $a$ and $b$ are known. As you remarked, ...
8
If your FSM is a DFA, then this is the Minimum Consistent DFA Problem, which is well known in the machine learning community. This problem is NP complete
Gold1978 - Complexity of Automaton Identification from Given Data.
The problem is also known to be hard to approximate within any polynomial factor. Indeed it is even hard to find an NFA whose number of ...
7
Weak duality is a property stating that any feasible solution to the dual problem corresponds to an upper bound on any solution to the primal problem. In contrast, strong duality states that the values of the optimal solutions to the primal problem and dual problem are always equal.
Was this helpful enough?
7
Quantum annealing essentially offers a square-root speed-up over classical simulated annealing in many circumstances. So, yes, it is potentially a faster approach for some optimization problems, but the speed-up isn't enough to make most hard problems tractable.
Unfortunately, you cannot efficiently simulate quantum annealing classically, because any ...
7
Adiabatic quantum computing (AQC) is a computational model (as Peter said in the comments). Compare AQC with other models of computation such as:
circuit-based quantum computing (CBQC)
Adleman-Lipton model (a model for computing using DNA)
Turing machine model (a model where computations are done with symbols on a tape)
One can devise algorithms using ...
7
It's NP-hard.
Here's a reduction from the feasibility version of Binary Integer Programming (BIP), which is NP-hard. The problem is to decide if there's a feasible solution to the constraints $Ax \leq b$ and $x_i \in \{0,1\}$. It's easy to convert this to a problem with the constraints $Ax \leq b$ and $x_i \in \{-1,1\}$.
Now consider the following ...
7
The problem as presented is NP-hard.
Suppose we have $f(y)=0, y\leq 1$ and $f(y) = y, y > 1$. Now if we have the constraints $y_1 + y_2 \geq 2.01$ and $y_i \geq 0$, and we want to minimize $\sum_i f(y_i)$, clearly we should choose one of these $y_i$ to be $1$ and one to be $1.01$.
Now, suppose we have a graph $G$, and we put a constraint like this for ...
7
[Since I could not edit my comment, I repost it here as an answer]
To determine if a quadratic program (QP) has multiple solutions (so you have to answer "Yes" if the QP has more than one solutions, and "No" if it has one or no solution) can be shown to be NP-complete by modifying the proof on NP-completeness of QP here http://link.springer.com/article/10....
Only top voted, non community-wiki answers of a minimum length are eligible
