Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.

# Questions tagged [np-hardness]

Questions related to NP-hardness and NP-completeness.

560 questions
Filter by
Sorted by
Tagged with
95 views

### What is the recognition complexity of k-uniform k-partite hypergraphs? [duplicate]

We can easily recognize bipartite graphs, but I surprisingly couldn't find anything on the recognition complexity of 3-uniform tripartite hypergraphs, though I'm sure this has been studied. It's also ...
257 views

### NP-hardness on Cayley graphs

What is known about complexity of NP-hard problems on Cayley graphs? Suppose that the graph is given explicitly as the multiplication table of the group and the list of generators. So the input ...
74 views

### Constant Width Max Sum Product Multi-objective Shortest path problem

This question is a follow-up on the question I asked three days ago here. For convenience I restate it here. I am given a graph. Each edge is labelled by a vector of numbers, called weights. They ...
158 views

### Max Sum Product Multi-objective Shortest path problem

Is anything known about the following problem: I am given a graph. Each edge is labelled by a vector of numbers, called weights. They are numbers between 0 and 1. A path is first assigned a vector, ...
2k views

### Can you identify the sum of two permutations in polynomial time?

There were two questions asked recently on cs.se which were either related to or had a special case equivalent to the following question: Suppose you have a sequence $a_1, a_2, \ldots a_n$ of $n$ ...
53 views

### About increasing the objective values of certificates for Max-Clique SDP

Say you write a round-k Lasserre (or any other hierarchy!) SDP relaxation of the Max-Clique problem. Lets say one now finds (or knows how to sample with high probability) a graph $G_1$ of size $n$ and ...
84 views

### Max common sub forest on $k$ graphs

Not sure how to phrase this really, but here goes. Suppose you are given $k$ simple graphs, each having exactly $m$ edges. The edges in each graph are labeled from 1 to $m$. The problem is to find ...
181 views

### NP-hardness of approximation for unconstrained submodular maximization

The problem of unconstrained submodular maximization can be phrased as follows: Given a non-negative submodular function $f$ on a domain $D$ find a set $S \subseteq D$ maximizing $f(S)$. Here a ...
2k views

### Do many-one reductions and Turing reductions define the same class NPC

I wonder if NPC classes defined by many-one reductions and Turing reductions are equal. Edit: Another question, are Turing reductions only collapsing C and co-C classes for some C or is there a class ...
267 views

### Variant of Subset Sum Problem with Changing Bound

Given a sequence of decreasing integers, i.e., $a_1 \geq a_2 \geq \cdots \geq a_T$ and a positive real $k\geq 1$, find a subset $S$ such that $$\max_{S\subseteq \{1,\ldots,T\}} \sum_{i\in S} a_i$$ ...
218 views

663 views

### Deeper look at Algorithmica?

Russell Impagliazzo published "A Personal View of Average-Case Complexity" (preprint) back in 1995. He presented five possible worlds we could be living in, depending on how P and NP were related. The ...
1k views

### “All-different hypergraph coloring” - known problem?

I am interested in the following problem: Given a set X and subsets X_1, ..., X_n of X, find a coloring of the elements of X with k colors such that the elements in each X_i are all differently ...
291 views

### Huffman Tree Depth, Is there any theory?

I'd like to as a variation on this question regarding Huffman tree building. Is there any theory or rule of thumb to calculate the depth of a Huffman tree from the input (or frequency), without ...
142 views

### Quantum computer versus Random 3-SAT?

It seems to be commonly believed that quantum computer cannot efficiently solve NP-hard problems. What about the challenging problems in average-case, such as Planted Clique and Random 3-SAT?
209 views