Questions tagged [np-hardness]

Questions related to NP-hardness and NP-completeness.

Filter by
Sorted by
Tagged with
-2
votes
0answers
28 views

A $TM$ definition on approximation solutions to optimization problems

It looks like we are defining approximation solutions as a witness specifying program. We want to find a witness which agrees within some approximation of optimal. Is it possible to specify as '...
0
votes
0answers
72 views

Is the traveling salesman problem still NP-hard if all edges need to be covered as well?

If we formulate the travelling salesman problem with an added edge-covering constraint as follows, is it still NP-hard? Given a graph G with non-negative edge weights, is there a circular walk in G ...
0
votes
1answer
50 views

How hard is deciding the existence of a polygonization with prescribed perimeter?

Polygonization problem of a set of points in the Euclidean plane (2D lattice) is to find a simple polygon that passes through all points. Deciding the existence of a polygonization with minimum (or ...
6
votes
1answer
183 views

Why does Dinur's proof of the PCP theorem fail to work for unique games?

What is the critical step where things go wrong if one attempts to use Dinur's proof the PCP theorem to prove the unique games conjecture by starting from a unique label cover instance and doing gap ...
7
votes
1answer
292 views

Is solving the following system of boolean equations NP-hard?

I reduced a problem I'm currently working on to the following system of boolean equations: $$ X_i \iff \begin{cases} \bigvee_{B \in A_i} \bigwedge_{k \in B} X_k \\ true \\ false \end{cases} $$ Where $|...
1
vote
0answers
135 views

What does it mean by the statement: “a problem is hard to approximate ”?

In most of the research papers that I have read so far, I often come across the statement of the following form: "the problem is hard to approximate within any factor smaller than some constant&...
1
vote
0answers
96 views

reordering a DAG with the minimum changes

Consider a DAG $(V,A)$ with an initial permutation $(v_1,v_2,…,v_n)$. We want to arrange the $n$ vertice in topological order while keeping as many vertices as possible. The problem is: Is it NP-hard ...
4
votes
1answer
229 views

3-SAT mixed with 2-SAT formulas

Context: Refering to the question: Complexity of the $(3,2)_s$ SAT problem? and since the paper by Porshen and Speckenmayer : Satisfiability of mixed Horn formulas, we know that even when $F_3$ is ...
0
votes
0answers
74 views

Is finding the optimal ordering of predicates NP?

Assume we want to find the elements from a set of elements $\mathscr{E}$ for which all predicates from a set of $n$ predicates $\mathscr{P}$ evaluate to true. In programming terms, we want to compute <...
12
votes
1answer
193 views

Why is the reduction from 3-SAT to 3-dimensional Matching Parsimonious?

In this talk at the Simons Institute, Holger Dell notes that there is a parsimonious reduction from 3-SAT to the 3-dimensional Matching (3-DM) problem. In other words, there is a reduction between ...
2
votes
1answer
94 views

Complexity of acyclicity of a “nondeterministic” graph

By "nondeterministic" I mean the graph is a collection of sets of "candidate" edges sharing a single destination: $E \subseteq 2^V \times V$. The problem is whether it is possible ...
1
vote
1answer
174 views

Is the knapsack variant with small profit and unlimited repetition of items NP-hard?

Consider the unbounded Knapsack problem where we are given $n$ items of integral weights $w_i$, integral profits $p_i$, and a max weight $W$. The goal is to maximize the total profit $\sum_i x_ip_i$ ...
6
votes
2answers
328 views

find the most similar topological ordering of a dag

Given a permutation $L$ of the $n$ vertices of the directed acyclic graph $G=(V,E)$. Question: is it NP-hard to find the topological order of the $G$ that is the most similar to the given permutation $...
3
votes
1answer
102 views

Parametrized complexity of sparse optimization

Optimization problems of the type: minimize $c^T x$ subject to [maybe some linear constraints and] $||x||_0\le k$ are known to be NP-hard. [Actually, I just realized that I don't have a reference, so ...
4
votes
1answer
129 views

Neighborly properties in a bipartite graph

Input: Let $G$ be a connected, bipartite graph with parts $A$ and $B$, each of size $n$. For a set of vertices $S$, let $N(S)$ be its set of neighbors. Question: Decide whether there exists a subset $...
-5
votes
1answer
104 views

Is mathematical proof itself NP-hard?

At the 8:00 mark of this video, he claims that proving things is itself an NP problem. I'm looking for more insight into this. Could someone help explain this concept to me and also provide a link to ...
0
votes
1answer
112 views

Minimizing the gaps with incremental capacity

There are a single job, a machine and a set of $n$ slots. The machine has a capacity that increments by $\zeta(t)$ every slot $t=1,2,\ldots,n$. Initially (before the first slot), the machine has 0 ...
1
vote
1answer
98 views

On the paper “Quantum Computing Hamiltonian cycles”

The paper Quantum Computing Hamiltonian cycles claims: An algorithm for quantum computing Hamiltonian cycles of simple, cubic, bipartite graphs is discussed. It is shown that it is possible to evolve ...
9
votes
1answer
200 views

Recent progress on the next-to-shortest-path problem for directed graphs?

In the paper "Computing strictly-second shortest paths" (1997), Lalgudi and Papaefthymiou consider the following problem: Let $G$ be a directed graph with edge-weighting $w$. Let $u,v$ be vertices in ...
1
vote
1answer
84 views

Choosing one number from each set so that the sum of squares of each distinct number counts is minimized

Problem is as follows: We are given $K$ subsets of $\{1,2,...,n\}$. We need to pick one number from each of these subsets such that $\sum_{i=1}^n p_i^2$ is minimized where $p_i$ is the number of times ...
-1
votes
1answer
182 views

Conjecture about ASP reductions between NP-complete problems

$ASP$-complete reductions, introduced by Ueda and Nagao, relate the hardness of computational problems in $FNP$. Basically, $ASP$-reduction is a polynomial time reduction between instances and a ...
0
votes
0answers
41 views

Would a machine learning algorithm benefit from an “optimization oracle”?

I'm trying to understand the behavior of machine learning algorithms where the loss function is non-convex and the problem of training the ML on a specific data set is computationally hard. Now let'...
-5
votes
1answer
26 views

Polynomial-time reducibility of Primality and 3-SAT

Is 3-SAT $\leq_{p}$ Primality? And/or is Primality $\leq_{p}$ 3-SAT? I think the answer is no and yes, respectively, but I'm not sure. Any help would be appreciated. Thank you.
5
votes
2answers
164 views

Topological sorting of a DAG where special vertices have to come in even groups

Consider the following problem. The input is a directed acyclic graph (DAG) $G = (V, E)$, and a subset $V' \subseteq V$ of vertices, which we call special vertices. The question is to determine ...
0
votes
0answers
88 views

NP-Hard or PTIME?

I am working on my research problem that essentially boils down to the following question. Consider an $N \times N$ matrix. There is a man at given a starting point $(x,y)$. In each unit of time, the ...
2
votes
1answer
198 views

Is $\{0,1\}$-Vector bin packing NP-Hard when vectors have constant dimension?

The paper https://cs.brown.edu/people/seny/pubs/vbponline.pdf discusses $\{0,1\}$-Vector Bin packing in the online setting and give lower bounds. However, they do not mention anything about the ...
-1
votes
1answer
61 views

Is it possible to approximate the solution of NP-Hard problems in polynomial time using linear programming? [closed]

Suppose we have a NP-Hard problem such as the k-col, which is meant to determine if a graph may be colored using at most ...
2
votes
1answer
86 views

NP hard proving: separate graph into a set of the same size disjoint parts by maximizing the shared neighbours of each part

Given a graph $G=\{V,E\}$ where $V$ denotes the nodes and $E$ denotes edges. The size of the node $|V| = nk$. The target is to separte the graph into $n$ disjoint parts $P=\{V_i\}_{i=1}^n$ and the ...
3
votes
1answer
82 views

Interval partitioning with restrictions: NP-complete or efficiently solvable?

The interval partitioning problem can be solved efficiently using a greedy algorithm. However, adding restrictions on the interval assignment to the problem results in a problem that appears harder. ...
3
votes
0answers
72 views

Uniformly sampling or counting connected graph partitions with any number of blocks

Question: Is it possible to uniformly sample in polynomial time from the set of all connected partitions of a graph? Or is there a JVV type argument that proves this to be NP-hard? To clarify: By a ...
2
votes
1answer
71 views

3-dimensional matching variant

In the normal version of the matching problem, we are given a set of vertices $X$, $Y$, and $Z$, each of size $n$, and a set of edges $E\subseteq X\times Y\times Z$. We need to find a matching $M\...
3
votes
1answer
115 views

What is the complexity of this weighted b-edge matching problem?

I'm wondering about the complexity of the following variant of the Generalized Weighted b-edge Matching problem: Input: An undirected multigraph $G = (V, E)$ without loops, an edge partition $(E_1,...
0
votes
2answers
114 views

Order of quantifiers in the definition of NP-completeness: does the reduction allow arbitrary polynomials? [closed]

Arora and Barak define NP-completeness as the following: "We say that a language $A \subseteq \{0, 1\}^∗$ is polynomial-time Karp reducible to a language $B \subseteq \{0, 1\}^∗$ denoted by $A \leq_p ...
2
votes
0answers
95 views

Complexity of a scheduling problem with a fixed left bound of jobs

Consider the following scheduling problem. We have a finite set of jobs $\mathcal{J}= \{j_1, j_2, ..., j_n\}$ to do. Every job $j_i$ has its own value $c_i$ (the amount of money we are paid for ...
7
votes
5answers
432 views

NP-complete decision problems on deterministic automata

Do you know any NP-complete decision problems on deterministic automata? Most NP-complete problems that come to my mind are either (see, or here) graph theoretical, or involve some string rewriting or ...
7
votes
1answer
293 views

Complexity of constructing minimum depth decision trees

I am interested in the computational complexity of Problem 1: Given a finite, non-empty set $J$, given $A, B \subseteq \{0,1\}^J$ such that $A \cap B = \emptyset$, and given $n \in \mathbb{N}$, does ...
-3
votes
1answer
109 views

is this selection problem np-hard? [closed]

Give $n$ clusters $C=\{C_i\}_{i=1}^n$ where each cluster consists of a set of similar points, i.e., $C_i=\{c_j\}_{j=1}^{|C_i|}$. The similarty between two points $c_i$ and $c_j$ is denoted as $w(c_i,...
3
votes
3answers
476 views

Best parameterized algorithm for maximum clique

I have seen the basic algorithm for the maximum clique problem parameterized by the maximum degree at an algorithms course. However, I struggle to find anything better. Searching for things like "...
0
votes
1answer
110 views

Is the counting version of 1-in-3 Sat #P-complete?

In the paper "Hard Tiling Problems with Simple Tiles", Moore and Robson prove that Cubic Planar Positive 1-in-3 Sat in NP-complete by a reduction from Positive 1-in-3 Sat. Cubic Planar Positive 1-in-...
0
votes
0answers
88 views

NP-Hard Knapsack Instances

Consider the classic Knapsack optimization problem (KP): Given $p_1, \dots, p_n, w_1, \dots, w_n, B\in\mathbb N$, compute a solution $I\subseteq \{1,\dots,n\}$, such that $\sum_{i\in I} w_i \leq B$ ...
6
votes
1answer
96 views

Determining if a word of specific length exists that is not accepted by a NFA

It is known that the problem of determining if an NFA accepts every word is PSPACE-COMPLETE, meaning it is also NP-Hard, but is this weaker version of the problem still NP-hard? Given an NFA and a ...
0
votes
0answers
63 views

Complexity of multi-objective optimization problems

How can we define and prove the worst-case complexity of multi-objective optimization problems (MOOP)? It is easy to see that, if one of the objectives is an NP-Hard optimization problem, then the ...
1
vote
1answer
143 views

The decision procedure of theory of closed real field is in NP-hard?

The decision procedure of theory of closed real field refers to https://en.wikipedia.org/wiki/Decidability_of_first-order_theories_of_the_real_numbers
4
votes
1answer
127 views

Hardness of finding if a vertex lies on a simple directed path between two vertices

Given a directed graph $G = (V, E)$ and three vertices $u, v, w \in V$. Is it NP-Hard to find whether there is a simple path from $u$ to $v$ passing through $w$? I found a couple of hardness ...
9
votes
2answers
123 views

Complexity of finding an edge set yielding specified vertex degrees

I'm trying to figure out if the following two problems are known in general to be in P or NP-complete: Q1: Given a graph $G=(V,E)$ and integers $d_i,\,1\leq\,i\leq|V|$, does there exist a subset $E'\...
6
votes
2answers
148 views

$NP$-Completeness of $\epsilon$-balanced graph partitioning for fixed $\epsilon$

Consider this graph partitioning problem: Let $G = (V, E)$ be a simple undirected graph and $0 \leq \epsilon \leq 1, M \geq 0$ be constants. Are there disjoint subsets $V_1, V_2$ with $V = V_1 \cup ...
12
votes
0answers
141 views

NP-Hardness of 4-cycle packing problem in complete bipartite digraph?

A directed complete bipartite graph is a bipartite graph where there is exactly one directed edge between any two vertices from its two different parts. In other words, it's an orientation of a ...
10
votes
1answer
721 views

Relationship between two graph optimization problems

Let $Q$ be a polynomial time computable graph property of simple, undirected graphs. Consider the following two optimization problems on any input graph: P1. Find a largest induced subgraph of the ...
2
votes
0answers
76 views

How hard is it to approximate distance of linear code

I'm trying to figure out what is the current knowledge about how hard it is, given a generating matrix of a linear code over a field $F_{q}$, approximate it's distance. I of course found that ...
2
votes
1answer
144 views

What Is the Complexity of This Two-to-One Matching Problem?

Given a graph $G=(V,E)$ and a function $c:V\mapsto\{1,2\}$. The function $c(\cdot)$ divides the vertices into two disjoint sets $V_1$ and $V_2$, where for all $v_1\in V_1$, we have $c(v_1)=1$ and for ...

1
2 3 4 5
13