Questions tagged [np-hardness]

Questions related to NP-hardness and NP-completeness.

Filter by
Sorted by
Tagged with
3
votes
1answer
99 views

how to achieve a topological sort of an given sequence with minimum swaps

For example, given the constraints {$a<b,c<d$} and a sequence $[b,a,c,d]$. we just need swap $a$ with $b$ to get an topological sort, I want to ask how to find the sort solutions with minimum ...
2
votes
1answer
140 views

A least sized partition of a set under a distance metric

What is the worst case complexity of an algorithm to find a least partition of a set under a distance metric, described as follows: Input: A set $S=\{s_1,\ldots,s_n\}$, where the elements $s_i$ are ...
9
votes
1answer
151 views

Best known asymptotic PCP sizes / 3-SAT

What are the best known asymptotic upper bounds on sizes of probabilistically checkable proofs? Ideally, I am looking for a contemporary survey on this broad question, but if there is none, I am ...
1
vote
1answer
127 views

A dominate vector subset sum problem

Let $k$ be some constants (e.g. one can take $k=2$ for simplexity), for any $u,v\in \mathbb{R}$, we say $u$ dominate $v$ if $\forall 1\le i\le k,~ u[i]\ge v[i]$, write it as $u\succ v$. Consider the ...
9
votes
0answers
130 views

Complexity of fractional SAT

Let $(a, k)$-SAT be $k$-SAT with the promise that if there is there is a satisfying assignment, then there is such an assignment that satisfies at least $a$ literals of every clause. Can 3-SAT with $...
2
votes
0answers
106 views

Counting the maximum number of paths of length $n$ that differ in at least $k$ edges

What is known about the complexity of solving (or approximately solving) the following problem? INPUT: Graph $G=(V,E)$ and constants $L$ and $K$. OUTPUT: The maximum size of any set $S$ of simple ...
3
votes
0answers
59 views

Hardness of ancilla free quantum circuit extraction from circuit with ancillas

Is there any known result regarding the hardness of the following problem: Given a quantum circuit with ancillae implementing a unitary, find a quantum circuit that does not use any ancillae that ...
1
vote
0answers
57 views

Reasoning about NP hardness of optimization problems with closed form functions as input

(This may not be a research level question per se. I can delete this question if the community thinks this way too) I am trying to understand how to reason about hardness of optimization problems ...
3
votes
2answers
245 views

Finding a set which dominates the Minimum Dominating Set

Given an unweighted, undirected graph, a dominating set $S$ is a set of nodes such that every node is in $S$ or adjacent to a node in $S$. The dominating set problem is NP-hard, but I am considering ...
2
votes
1answer
133 views

Is partitioning a multiset into two multisets with equal averages NP-complete?

The subset sum problem of partitioning a multiset of integers into two multisets with equal sums is NP-complete. Is the seemingly related problem of partitioning a multiset of integers into two ...
4
votes
0answers
116 views

A variant of hitting set: finding a matching to hit all edge sets

In general, the hitting set problem is given a family $\cal S$ of sub-sets, $\{S_1, \cdots, S_h\}$, and a universal set $U = \bigcup_{i\in [1,h]} S_i$. It asks for a minimum set $H \subseteq U$ ...
-1
votes
1answer
78 views

Restricted Universe Exact Cover

Apologies for a simple question - I am a beginning graduate student in TCS. Consider the following $\mathrm{ExactCover}$ problem: Given a collection $\mathcal{S}$ of subsets of a universe set $U$ and ...
3
votes
0answers
208 views

What is consequence of $PH\subseteq NSPACE((\log n)^2)$?

What is consequences of $PH\subseteq NSPACE((\log n)^2)$? We don't even know PH is equals to L or not. I am wondering what will be happened when $PH\subseteq NSPACE((\log n)^2)$?
-5
votes
1answer
89 views

NP hard? Maximize the average for a subset of numbers

Given a set of real numbers, choose a subset to maximize the average subject to the average not exceeding a given threshold. Is it NP hard? I think so, but I cannot come out with a proof. Thanks a ...
16
votes
1answer
1k views

Password hashing using NP complete problems

Commonly used password hashing algorithms work like this today: Salt the password and feed it into a KDF. For example, using PBKDF2-HMAC-SHA1, the password hashing process is ...
22
votes
2answers
2k views

Are there any hard instances of 3-SAT when the clauses can only use literals that are “nearby” each other?

Let the variables be $x_1 , x_2 , x_3 ... x_n$. The distance between two variables is defined as $d(x_a , x_b) = |a-b|$. The distance between two literals is the distance between the corresponding ...
-1
votes
1answer
61 views

How to make any graph 2-degenerate?

I have to show a PPT(polynomial time reduction) from 'Colorful graph Motif' to '2-Degenerate Steiner Tree'. As input graph should be 2-degenerate, but here is normal graph G (that is, basically an ...
1
vote
0answers
98 views

Directed NP Hard Problem on DAG

There are problems that are NP-Hard on undirected graphs(maximum weight independent set and graph coloring) but are polynomial time solvable on trees. Tree decomposition is a good tool to talk about ...
3
votes
2answers
167 views

What is the best approximation and exact algorithm for vertex cover on cubic graphs?

"Best" = best performing in terms of run-time for exact algorithm and approximation ratio for an approximation algorithm.
-1
votes
1answer
53 views

NP-Complete graph problems where a special vertex is given as input?

I am currently working on a graph theory problem where the instance includes a graph and a special vertex in the graph. I am trying to prove the NP-completeness of the problem as well as explore ...
6
votes
1answer
113 views

NP completeness of classes of spanning trees

I am teaching a complexity course, and I want to give some examples of similar looking problems such that one is in P, and the other is NP complete. This made me think of the following problem: does ...
20
votes
4answers
851 views

Problems that are counter-intuitively solvable in practice?

Recently, I went through the painful fun experience of informally explaining the concept of computational complexity to a young talented self-taught programmer, who never took a formal course in ...
4
votes
1answer
189 views

How hard is it to determine the chromatic number of a unit distance graph?

For example, is it NP-complete to decide whether a unit distance graph is 3-colorable?
1
vote
1answer
88 views

Minimum number of columns making each row different

I'm curious whether this problem is NP-hard: suppose you are given an arbitrary $m\times n$ 0-1 matrix (each element is either 0 or 1, for the simplicity of the problem), and any pair of rows (i.e. a ...
1
vote
0answers
95 views

Best way to represent NP-Hardness result for decision problem with two decision parameters

What is the best way to represent a NP-Hardness result for a decision problem with two decision parameters? Suppose we have a problem $P$ which asks to minimize two parameters $x$ and $y$ and we show ...
0
votes
1answer
76 views

Constrained Topological Sorting with bounded number of chains

In general, constrained topological sorting is NP-hard. Now we add another constraint to it, such that take any k+1 nodes and there will be at least one pair ...
3
votes
0answers
82 views

PTIME or NP-Hardness of stochastic objective function

I will begin by linking a previous post where I asked a general question for a stochastic setting which I describe below. It turns out that my "proof" for a restricted case had a mistake and there is ...
3
votes
0answers
90 views

Showing hardness of maximizing stochastic objective function over graph

Consider a graph $G = (V, E)$ with $n$ vertices and $m$ edges. Each vertex $v_i$ can take positive value $a_i$ with probability $p_i$ and value $0$ with probability $1-p_i$. The challenge is to ...
1
vote
0answers
85 views

Is NP-complete the existence of paths of a given length in a directed graph? [closed]

Given a directed graph G= (V,E), a pair of vertices s and t, a natural number K encoded in binary, whether the problem to decide there exists a path (not necessarily simple) from s to t of length K is ...
4
votes
0answers
97 views

min weight k-closure on DAG

The problem Given a (connected) DAG $G(V,E)$ where each node is assigned an (non-negative) integer weight an integer k where $0\leq k\leq|V|$ Find a induced subgraph $H$ of $G$ consisting of $k$ ...
5
votes
1answer
570 views

Sparsification Lemma for k-SAT and Exponential Time Hypothesis

According to R. Impagliazzo, R. Paturi and F. Zane, 2001 an instance of $k$-SAT is called sparse if $m = O(n)$ where $m$ denotes the number of clauses and $n$ the number of variables. The ...
0
votes
1answer
68 views

About using smoothness of the Hessian for getting to approximate criticality of a non-convex objective

Is there any algorithm which shows that under the assumption of Lipschitz smoothness of the Hessian of a non-convex function one can get to its critical point faster?
5
votes
0answers
79 views

Complexity of bounded degree full contraction

This paper defines the problem $\mathrm{B{\scriptsize OUNDED} \ D{\scriptsize EGREE}\ C{\scriptsize ONTRACTION}}$ as follows: Instance: A graph $G$ and two integers $d$ and $k$. Question: Is there a ...
23
votes
2answers
513 views

Testing whether letters can be scheduled to achieve a word in a regular language

I fix a regular language $L$ on an alphabet $\Sigma$, and I consider the following problem that I call letter scheduling for $L$. Informally, the input gives me $n$ letters and an interval for each ...
1
vote
2answers
213 views

If only pathological cases of NP-hard problems are difficult to solve, then why isn't NP-hard defined to only include those pathological cases?

NP-hard problems are not used in cryptography, because they are believed to be computationally-intractable in the worst case but are not computationally-intractable in the average case. Is there a ...
10
votes
2answers
220 views

Common insights into hypothetical complexity of graph problems

I came across two examples of hypothetical hardness of some graph problems. Hypothetical hardness means that refuting some conjecture would imply the NP-completeness of the respective graph problem. ...
16
votes
1answer
426 views

What is the complexity of this graph problem?

Given a simple undirected graph $G$, find a subset $A\neq \emptyset$ of vertices, such that for any vertex $x\in A$ at least half of the neighbors of $x$ are also in $A$, and the size of $A$ is ...
1
vote
0answers
114 views

Generalized path cover problem in DAG

Let $G=(V,E)$ be a directed acyclic graph. Two vertices is transitive if there is a directed path between them. A Path Cover for a Set of Transitive Pairs (PCSTP) is a set of directed paths such that ...
1
vote
0answers
149 views

Are there any NP-complete for continuous mathematics? [closed]

Looking at this wiki page, it seems most NP-complete problems are based on discrete structures, such as graphs. What are some problems that involve real or complex analysis instead of discrete ...
5
votes
2answers
178 views

Minimising the root-set of a spanning hyperforest of a hypergraph

I am interested in the complexity of a problem involving spanning hyperforests (a union of hypertrees, which covers all of the vertices) of a $k$-hypergraph. I describe the relevant definitions for ...
2
votes
0answers
172 views

Is Non-linear Constrained Optimal Exact Cover NP-Hard?

Playing around I ran into a problem which looks like a Exact Set Covering / Partition Problem, but I am unable to find a reduction to categorize the complexity of the problem, despite it looks NP-Hard....
3
votes
0answers
141 views

Random self reducibility and NP

I was reading the Wikipedia page Random self-reducibility and it states: If an NP-complete problem is non-adaptively random self-reducible the polynomial hierarchy collapses to $\Sigma_3$. I am ...
13
votes
1answer
698 views

Complexity of the problem of words with fewest distinct letters accepted by a finite automaton

Given a finite (deterministic or nondeterministic, I don't think this has much importance) automaton A and a threshold n, does A accept a word containing at most n distinct letters? (By k different ...
3
votes
2answers
172 views

Reduction of graph chromatic number to hypergraph 2-colorability

I'm following this paper titled "Coverings and colorings of hypergraphs" by Lovasz 1973, which is referenced in Garey and Johnson's Computers and Intractability, for the Set Splitting Problem. In this ...
3
votes
1answer
175 views

Matrix Coloring under Vertical and Horizontal Constraints

I'm searching for the correct name of the following NP-complete problem. I would also appreciate answers pointing to problems with similar-looking variations. The input consists of A set of ...
-4
votes
1answer
62 views

Proving NP-complete problem

Suppose the following problem: Given an undirected graph G=(V,E), is it possible to choose a subset V' of vertex set V, such that deleting it removes all triangles (cycles of length 3), where |V'| is ...
5
votes
0answers
109 views

An optimal subspace projection problem

Suppose we have a $k$-dimensional subspace $V$ in $\mathbb{R}^n$ given by a basis $\{v_1,\cdots,v_k\in \mathbb{R}^n\}$, find an index set $I\subset [n]$ with $|I|=m$ where $k\le m\le n$, such that $$\...
0
votes
2answers
165 views

Geometric max cover

Consider $n$ points and a distance function $d$ that satisfies the triangle inequality. We are also given a number $r$. Each point $p$ defines a set $B_p$ (or a ball) that covers all other points ...
28
votes
1answer
1k views

Functions that are Not Efficiently Computable but Learnable

We know that (see, e.g., Theorems 1 and 3 of [1]), roughly speaking, under suitable conditions, functions that can be efficiently computed by Turing machine in polynomial time ("efficiently computable"...
7
votes
1answer
228 views

What are some problems in $P$ which have lower bounds assuming that $P \neq NP$ or the ETH?

Last year I had watched this talk online about problems in $P$ for which an algorithm which runs in some subclass of $P$, say in subquadratic time, would imply $P = NP$, or violate the ETH (...