As of May 31, 2023, we have updated our Code of Conduct.
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 ...
Joe Bebel's user avatar
  • 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 ...
David Eppstein's user avatar
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: ...
Andras Farago's user avatar
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'|$. ...
Yury's user avatar
  • 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 ...
Steven Stadnicki's user avatar
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 ...
usul's user avatar
  • 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 ...
David Eppstein's user avatar
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 ...
Emil Jeřábek's user avatar
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 ...
saisandeep's user avatar
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-...
user1271772's user avatar
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$ ...
David Eppstein's user avatar
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, ...
Mikhail Rudoy's user avatar
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 ...
Andras Farago's user avatar
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, ...
user541686's user avatar
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)$...
Saeed's user avatar
  • 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 ...
Peter Shor 's user avatar
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 ...
David Eppstein's user avatar
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 ...
Peter Shor 's user avatar
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....
Clement C.'s user avatar
  • 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. ...
Chao Xu's user avatar
  • 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, ...
Neal Young's user avatar
  • 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
Kristoffer Arnsfelt Hansen's user avatar
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 ...
Thomas Kalinowski's user avatar
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 ...
Willem Van Onsem's user avatar
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 ...
Greg Kuperberg's user avatar
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 ...
Sasho Nikolov's user avatar
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. ...
Aryeh's user avatar
  • 10.2k

Only top scored, non community-wiki answers of a minimum length are eligible