43
votes
Accepted
Is it a rule that discrete problems are NP-hard and continuous problems are not?
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 ...
- 2,295
26
votes
Is it a rule that discrete problems are NP-hard and continuous problems are not?
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 ...
- 50.6k
16
votes
Easy to optimize but hard to evaluate
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: ...
- 11.1k
14
votes
Accepted
Is the following graph optimization problem approximable within a constant factor?
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'|$. ...
- 3,899
13
votes
Is it a rule that discrete problems are NP-hard and continuous problems are not?
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 ...
- 1,356
10
votes
Accepted
Find research partner (profession and beginner)
I don't know of such a page. Most researchers have specific problems that they are interested in working on, and would only want to collaborate on those. If you pick a particular area and focus on ...
- 7,175
9
votes
Accepted
Minimum weight matching in general graphs with additional input specifying the number of matched edges
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 ...
- 50.6k
9
votes
Accepted
Positivstellensatz and sum of squares method
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 ...
- 15.6k
9
votes
Accepted
Proof that the graph optimization problem is NP-hard
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 ...
- 126
8
votes
Accepted
Quantum annealing vs adiabatic quantum computation
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-...
- 541
8
votes
Second Smallest $s$-$t$-Cut in a Network
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$ ...
- 50.6k
8
votes
Solving linear equations involving min
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, ...
- 2,758
8
votes
Complexity class of optimization problems whose fractional relaxation is polynomial-time solvable
The answer to the second question is no. Here is an example when the integer-output optimization problem is polynomial-time solvable, yet its fractional relaxation is NP-complete:
In complements of ...
- 11.1k
7
votes
Is it a rule that discrete problems are NP-hard and continuous problems are not?
Discrete problems typically tend to be harder (e.g. LP vs. ILP) but it's not the discreteness itself that's the problem... it's how the constraints affect how you can search your domain. For example, ...
- 421
7
votes
Accepted
Finding the two shortest paths while minimizing the number of nearby/common edges
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)$...
- 3,430
7
votes
Accepted
Is finding an optimal solution to this Knapsack-like problem NP-hard?
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 ...
- 23.9k
7
votes
What is this graph problem, and how hard is it?
In "Optimization procedures for the bipartite unconstrained 0-1 quadratic programming problem" [Comput. Oper. Res. 51, 2014, pp. 123–129] the authors Abraham Duarte, Manuel Laguna, Rafael ...
- 50.6k
6
votes
What are some of the most ingenious linear programs developed for tackling hard combinatorial problems?
The relaxation of Calinescu, Karloff and Rabani for the undirected Multiway Cut problem is one my favorites. Had a big influence on subsequent work.
http://www.sciencedirect.com/science/article/pii/...
6
votes
Accepted
What do you call the join of two optimization problems?
I think this falls in the category of multi-objective function optimization problems.
To be specific, it's a linear scalarization of an optimization problem with two objective functions.
I don't ...
- 23.9k
6
votes
Accepted
Minimizing a submodular function given noisy oracle access
A FOCS'15 paper by Lee, Sidford, and Wong [LSW15] can be leveraged to obtain such minimization guarantees -- cf. Section 5 (specifically, Corollary 5.4) in our recent paper ([BCELR16]).
Corollary 5....
- 4,431
6
votes
Accepted
Modifying Edmonds' Blossom Algorithm
You just have to solve the following problem: Find a matching of size exactly $k$ with minimum weight.
It can be solved by reducing to min weight perfect matching. See the paper by Ján Plesnı́k. ...
- 4,367
6
votes
Accepted
Characterization of integral polyhedra
Here's a proof (sketch) that doesn't explicitly use duality. More precisely, it replaces duality by a seemingly weaker (and hopefully easily believable) geometric fact, in Step 3 below.
EDIT: But, ...
- 9,555
6
votes
Accepted
Hardness of maximizing $x^TAy$ with $\{-1,1\}$ entries
NP-hardness is proved by Roth and Viswanathan in the paper On the hardness of decoding the gale-berlekamp code
5
votes
Is the complexity of this covering problem known?
The problem is known as the propagation problem. Aazami has proved in his PhD thesis that the weighted version is NP-complete even when the graph is planar and the node weights are in $\{0,1\}$. The ...
- 1,026
5
votes
Is it a rule that discrete problems are NP-hard and continuous problems are not?
Although for some popular problems, it is indeed true, I think both assumptions are - depending on what you define as an optimization problem - not true.
First some definitions: most optimization ...
- 377
5
votes
Approximately sampling from convex polyhedrons with quantum computers
As the post acknowledges, the existence of a classical polynomial-time algorithm to estimate the volume of a convex polytope is a game-changer. A quantum algorithm is much less likely to be ...
- 451
5
votes
What are some of the most ingenious linear programs developed for tackling hard combinatorial problems?
Some of the linear programs which comes to my mind are
George Dantzig’s linear program for Traveling Salesman Problem. You can find a nice description of the result here.
Flow based Linear program ...
5
votes
Centroid in $\ell_2$ distance
This is the geometric median problem. There is a nearly linear time algorithm based on interior point methods due to Cohen et al.: to find a $(1+\varepsilon)$-approximation their algorithm runs in ...
- 18.1k
5
votes
Accepted
Understanding the No Free Lunch Theorem
You're asking about optimization and universal search, BUT machine-learning is tagged and you're wondering about "a uniform distribution on an infinite" discrete set so perhaps this will be helpful. ...
- 10.2k
Only top scored, non community-wiki answers of a minimum length are eligible