Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [np-hardness]

Questions related to NP-hardness and NP-completeness.

1
vote
1answer
259 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 ...
10
votes
1answer
226 views

Complexity of digraph homomorphism to an oriented cycle

Given a fixed directed graph (digraph) $D$, the $D$-COLORING decision problem asks whether an input digraph $G$ has a homomorphism to $D$. (A homomorphism of $G$ to $D$ is a mapping $f$ of $V(G)$ to $...
1
vote
0answers
139 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?
5
votes
1answer
200 views

Graph class with easy chromatic number, but NP-hard coloring

Is there a graph class for which the chromatic number can be computed in polynomial time, but finding an actual $k$-coloring with $k=\chi(G)$ is NP-hard? Without any further restriction the answer ...
-4
votes
1answer
194 views

NP-completeness of one generalized subset sum problem (target sum belongs to interval) [closed]

I need to prove that decision problem: for a given set of positive integers $a_1, ..., a_n$, does it exist a subset that sums up to a value within interval $[\frac{1}{2}\sum a_i; \frac{1}{2}\sum a_i+...
3
votes
0answers
125 views

Complexity of minimizing monotone arithmetical formulas

Let's say that I have a multi-variate arithmetical expression $A(x_1, \ldots, x_n)$ that uses addition and multiplication operations and is also in a very simple form of sums of products, e.g., $A_1(...
8
votes
1answer
207 views

Complexity of a graph-rewriting problem

I recently came across the following problem which seems to fall in the context of graph rewriting problems: Input: A graph $G=(V,E)$ with maximum degree 3, an edge $e_0 \in E$ and pairs of graphs $(...
8
votes
1answer
263 views

BQP algorithm for two graph bisection problems and its implications on NP $\subseteq$ BQP

I read the paper Ahmed Younes, "A Bounded-error Quantum Polynomial Time Algorithm for Two Graph Bisection Problems", 2015. doi:10.1007/s11128-015-1069-y which is published in Springer's journal ...
2
votes
1answer
320 views

Is there a FNP problem that's NP-hard but not FNP-hard?

For the reductions, choose a class C such that [it's clear what FC means] and FC is not known to be able to solve the satisfaction search problem, and assume that FC indeed can't solve that search ...
4
votes
1answer
225 views

Find worst case input for a program solving an NP-hard problem

I am trying to find a way to find a worst-case input for a black-box implementation of an algorithm with worst-case exponential runtime. The problem that the program solves (integer linear ...
13
votes
4answers
797 views

Finding the sparsest solution to a system of linear equations

How hard is it to find the sparsest solution to a system of linear equations? More formally, consider the following decision problem: Instance: A system of linear equations with integer coefficients ...
5
votes
2answers
185 views

Popular average-case complexity assumptions

Except for planted clique and random 3SAT, what are the other commonly used average-case complexity assumptions?
4
votes
2answers
231 views

Partition graph into 2 or more claw-free subgraphs

Is it NP-hard to partition the vertex set of graph G into k subsets so that they induce k claw-free subgraphs of G?
2
votes
0answers
121 views

Empty sudoku and NP-completeness [closed]

My question is straightforward: Is an empty sudoku grid (not partially completed) still NP-complete?
4
votes
1answer
242 views

Bipartite Graphs - Maximum subset of one partition with at most n neighbours - NP-hard?

Given: A bipartite graph G=(U,V,E) Integers n and k. Decision Problem: Is there a subset of U of size k that has at most n neighbours? I am trying to figure out whether this problem is NP-hard (...
1
vote
1answer
258 views

Is this problem #P-hard and why?

Problem: In a directed graph $G=(V,E)$, each edge $e\in E$ is associated with a weight $w_e$ which is geometrically distributed with a parameter $p$, i.e. $P(w_e=i)=p(1-p)^{i-1}, i\geq 1$. $s,t$ are ...
1
vote
0answers
60 views

Multicuts (or multiway cuts) for 3 Terminals of Minimum Capacity

For each fixed $k \geq 3$, the following well-known problem is NP-complete. k-Multicut (aka "Multiway Cut", "k-Way Cut", "Multicut") Input: $(N,l)$ where $N=(V,E,T,c)$ is an undirected $k$-terminal ...
6
votes
1answer
290 views

NP-hardness of coloring uniform hypergraphs

Since a $2$-uniform hypergraphs are just graphs. The problem of deciding if $2$-uniform is $k$-colorable for $k=1,2$ is easy, and NP-hard for $k \geq 3$ colors. This is well know and I have seen ...
3
votes
1answer
191 views

A maximization problem containing summation and multiplication

Are the following two problems NP-hard? Problem 1 Given $n$ ordered pairs of integers $S=\{(a_i,b_i)\}$, $1\leq i \leq n$, and an integer $k$. Find a subset $A$ of $S$ with $k$ elements, such that $...
7
votes
0answers
1k views

Reduction from Vertex Cover to Max-Cut? [closed]

I am referring to Computational Complexity by Arora and Barak for my course. In the section on NP-completeness reductions, the book has a diagram that is represents how one NP-complete problem ...
14
votes
0answers
544 views

Does solving matrix multiplication in quadratic time imply that SETH is false?

I have a little conjecture that if you could perform matrix multiplication (or solve 3-clique) in $O(n^2 \log(n))$ time, then you could solve CNF-SAT in $O(2^{(1-\epsilon)n})$ time. In other words, ...
0
votes
0answers
33 views

On approx-preserving P- and A-reducibilities

Let $X$ and $Y$ be two NPO problems. Let $(f,g)$ be a reduction between $X$ and $Y$, in particular, assume that $(f,g)$ is both P-reduction and A-reduction, i.e., there exist two poly-time ...
12
votes
1answer
312 views

Sampling a uniformly random satisfying assignment

Problem: Given $\phi : \{0,1\}^n \to \{0,1\}$ represented by a boolean circuit, generate a uniformly random $x \in \{0,1\}^n$ such that $\phi(x)=1$ (or output $\perp$ if no such $x$ exists). Clearly ...
3
votes
1answer
197 views

How hard is recognizing a permutation that is a square for the shift product?

This is a continuation of my attempts to generate simple combinatorial computational problems that turn out to be computationally hard (NP-complete). In this pursuit, I came up with a permutation ...
2
votes
1answer
165 views

When can a convex function induce submodularity?

Say I have a real valued convex function $f$ on the hypercube $[-1,1]^n$. Let $f'$ be the induced function on the discrete hypercube $\{-1,1\}^n$. Now I want to find a vertex on $\{-1,1\}^n$ on which ...
22
votes
1answer
617 views

Is it still open to determine the complexity of computing the treewidth of planar graphs?

For a constant $k \in \mathbb{N}$, one can determine in linear time, given an input graph $G$, whether its treewidth is $\leq k$. However, when both $k$ and $G$ are given as input, the problem is NP-...
3
votes
0answers
54 views

Is this permutation-sum problem NP-complete? [duplicate]

A new, tighter tardiness bound has been found for global Earliest-Deadline-First scheduling of jobs on symmetric multiprocessors. But this bound seems to be particularly hard to compute. In particular,...
6
votes
0answers
567 views

Is this permutation-sum problem NP-complete?

A new, tighter tardiness bound has been found for global Earliest-Deadline-First scheduling of jobs on symmetric multiprocessors. But this bound seems to be particularly hard to compute. In particular,...
11
votes
2answers
233 views

Determining what can be achieved by a permutation of elements of a noncommutative group

Fix a finite group $G$. I am interested in the following decision problem: the input is some elements of $G$ with a partial order on them, and the question is whether there is a permutation of the ...
4
votes
2answers
349 views

Graph coloring/partitioning problem

I'm interested in the complexity of the following problem: Problem $P$: Given an undirected planar graph $G=(V,E)$ and a weight function $w: E \rightarrow \mathbb{Z}$ (so weights can be negative, ...
2
votes
0answers
207 views

Convex hull of polytopes

Consider a set of polytopes $P_i : i=1,2,...,k$ each of which has a structure as $P_i:= \{(x_{i1},x_{i2},..., x_{in})\; |\; x_{ij} \in [a_{ij}, b_{ij}] \subseteq [0,1]\}\;\; \text{for all}\;\; j=1,......
-1
votes
1answer
300 views

What is the simplest known solver for a np-complete problem?

Lets define the simpler of two terms as the one with shortest description length on the untyped λ-calculus. Trying to find the simplest solver for a np-complete problem, I've got this: ...
3
votes
2answers
172 views

Is this covering problem NP-hard?

Given a rectangular region $R$ and a set $D$ of $n$ disks such that the union of all disks in $D$ cover the entire rectangular region $R$, the objective is to find the minimum cardinality set $D'$ ...
0
votes
0answers
154 views

NP-hardness of minimizing sum of complicated objective function

In our research, we faced the following problem optimization problem: Input: a list of $k$ pairs of positive integers $(n_1,d_1), \ldots, (n_k,d_k)$; an integer $m$. Output: $P$, a partition of the ...
4
votes
0answers
133 views

What is the current “state-of-the-art” solver for quadratic knapsack problems?

New to this forum, so please let me know if my question format is incorrect. For linear KP with $n$ items and $c$ capacity, dynamic programming can find exact solutions in $\mathcal{O}(nc)$. I have ...
4
votes
1answer
582 views

If BQP contains NP, does this mean that P=NP?

There is a question raised by Scott Aaronson in one of his papers [1]: "Could we show that if NP ⊆ BQP, then the polynomial hierarchy collapses?". Assuming the answer is yes, and it is also know that ...
13
votes
2answers
3k views

Lexicographically minimal topological sort of a labeled DAG

Consider the problem where we are given as input a directed acyclic graph $G = (V, E)$, a labeling function $\lambda$ from $V$ to some set $L$ with a total order $<_L$ (e.g., the integers), and ...
1
vote
2answers
1k views

Is longest common subsequence with bounded occurrences NP-complete?

The general longest common subsequence problem (LCS) over a binary alphabet is NP-complete. Does the problem remain NP-complete if each input string has m zeros and n ones, where m and n are constants?...
4
votes
1answer
177 views

Is SAT with two “opposite” solutions NP-hard?

Here is a variant of the SAT problem in which a satisfying assignment must have additional properties. Input: A 3-CNF formula $f$ with variables $x_{1\dots k}$. Output: For an assignment $S$ of $x_{1\...
9
votes
1answer
382 views

Does 1-in-3 SAT remain NP-hard even if every variable occurs both positively and negatively?

The standard problem 1-in-3 SAT (or XSAT or X3SAT) is: Instance: a CNF formula with every clause containing exactly 3 literals Question: is there a satisfying assignment setting precisely 1 literal ...
5
votes
0answers
119 views

Completing a matrix (over the reals) to be singular

Consider the following problem: you are given a matrix (say, with rational entries) some of whose entries are actually left blank; can these blanks be filled in with real numbers so that the resulting ...
2
votes
0answers
150 views

Is the nonnegativeness of a polynomial hard for $\mathsf{NP}_\mathbb{R}$?

It is clear that the following problem is in $\mathsf{NP}_\mathbb{R}$. Input: a list $P$ of triplets $(a,s,t)$ where $s$ and $t$ are nonnegative integers. Output: is there an $x\in \mathbb{R}$ such ...
3
votes
0answers
201 views

NP-hardness of a quadratic programming problem

Motivated by the mean-variance optimization, I came up with the following question: Given $n$ integers $a_1, \cdots, a_n$; $n$ lower bounds $0<\ell_1, \cdots, \ell_n<1$ $n$ upper bounds $0<...
1
vote
1answer
230 views

NP-Hardness for an optimization problem

I want to prove that the following optimization problem is NP-Hard. max $\prod_{i = 1}^{N} \frac{\left[\sum_{j =1}^M x_j \mathcal{R}_{ij}\right]^2}{ \sum_{j=1}^M x_j}$ subject to $x_j \in \{0,1\}\...
9
votes
1answer
156 views

Edge-partitioning into rainbow triangles

I'm wondering if the following problem is NP-hard. Input: $G = (V,E)$ a simple graph, and a coloring $f : E \to \{1,2,3\}$ of the edges ($f$ does not verify any specific property). Question:...
25
votes
1answer
706 views

Recognizing sequences with all permutations of $\{1, \ldots, n\}$ as subsequences

For any $n > 0$, I say that a sequence $s$ of integers in $\{1, \ldots, n\}$ is $n$-complete if, for every permutation $\mathbf{p}$ of $\{1, \ldots, n\}$, written as a sequence of pairwise distinct ...
7
votes
1answer
210 views

What do we know about checking real-stability of multivariate complex polynomials?

Given a polynomial $p : \mathbb{C}^n \rightarrow \mathbb{C}$ it is to be called "real-stable" if (1) all its coefficients are real and (2) if it has no roots such that all the coordinates of the root ...
4
votes
1answer
170 views

Example of a function problem which is $\mathrm{FP}^{\mathrm{NP}}[wit, log]$-hard?

The usage of an $\mathrm{NP}$-oracles which delivers a witness has been proposed for example in [Buss1995]. I would like to see an example of an $\mathrm{FP}^{\mathrm{NP}}[wit, log]$-hard problem. Can ...
11
votes
0answers
313 views

a geometric variant of k-medians. NP-hard or in P?

The following problem is a special case of k-medians. Is it NP-hard? Is it in P? Input: $n$ points $(x_1,y_1), (x_2,y_2), \ldots, (x_n, y_n)$ with each $y_i \ge 0$, and an integer $k$. Output: a ...
1
vote
0answers
254 views

Finding an equivalent NP-complete instance for this game-theory problem

I apologize if this question is not a good fit for CSTheory. I'm a PhD student who has just started out and I'm working on a game-theory problem in one of my classes. Although my professor hasn't ...