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
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
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
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 ...
8
The second smallest cut, and more generally the $k$ smallest cuts, can be found in time polynomial in $k$ and the network size. See:
H. W. Hamacher. An $(K\cdot n^4)$ algorithm for finding the $k$ best cuts in a network. Oper. Res. Lett. 1(5):186–189, 1982, doi:10.1016/0167-6377(82)90037-2.
H. W. Hamacher, J.-C. Picard, and M. Queyranne. On finding the $K$ ...
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
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
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....
7
You might try one of the auction-based algorithms for bipartite matchings. (See e.g. lecture notes describing a simple variant here: https://staff.fnwi.uva.nl/n.s.walton/Notes/Bertsekas_Auction.pdf but more optimizations are possible).
These algorithms do not necessarily have the best worst-case running time, but require only very simple operations, and so ...
7
If the cost is $|P_1|+|P_2|+|P_1∩P_2|$, then a simple reduction to the shortest pair edge disjoint paths gives us a polynomial time solution. For each edge $e=(u,v)$ add two edges $(u,uv)$ and $(uv,v)$ each of them with same edge weight as $e$. The shortest pair edge disjoint paths in the new graph corresponds to the required solution in the original graph.
...
7
NOTE: My original reduction didn't work. Fixed now.
Can't subset-sum be reduced to this problem fairly easily? Suppose all the profits $v_i$ are the same, say $v_i = 1$, and all the profits $p_i$ are proportional to the weights, so
$p_i = \beta w_i$ with $\beta < 1$.
Now, if there's a set of weights $S$ such that $\sum_{i\in S} w_i = W$, you can get a ...
7
I assume the generalization you are thinking of is the following:
Given value $d$, and values $s_i$ and $r_i$ for $i = 1,2,...,k$, find (if possible) an $\alpha$ such that
$$\sum_{i = 1}^k\min(r_i, s_i\alpha) = d$$
Consider the expression $\min(r_i, s_i\alpha)$. This expression is sometimes equal to $r_i$ and sometimes equal to $s_i\alpha$, with a ...
6
One general approach to generating harder instances is as follows:
Start with a random problem instance.
Embed a "hidden backdoor": randomly choose a good solution (one that's likely to be much better than any solution that already exists) and modify the problem instance to forcibly embed this solution into the problem instance.
For instance, for TSP, you ...
6
In your example, you consider a size optimizer, that is a program that
takes a program $P$, and returns an equivalent program $P'$ such that there is no other program $P''$ also equivalent to $P$ but strictly smaller than $P'$.
With such a perfect size optimizer, you could build a decision procedure for this question
Is an input program $P$ ...
6
I don't know if you're still interested in this (old) question, and if I understood well the resource constraints you gave in the comment; however it seems that your problem (which is slightly different from usual RCSP problems) is NP-complete for planar (undirected or directed or directed acyclic) graphs of max-degree 3.
The easy reduction is from 3-SAT. ...
Only top voted, non community-wiki answers of a minimum length are eligible
