Questions tagged [np-hardness]

Questions related to NP-hardness and NP-completeness.

1
vote
0answers
76 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 ...
3
votes
0answers
84 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$ ...
4
votes
1answer
407 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
51 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 ...
22
votes
2answers
485 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
203 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
217 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
407 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
101 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
144 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
175 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
168 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
127 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
696 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
166 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
172 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
59 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
107 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
144 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"...
6
votes
1answer
221 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 (...
3
votes
2answers
203 views

Hardness of exact binomial tail bounds

Chernoff bounds, in their various forms, bound the tails of a Binomial$(n,p)$ random variable $B$. Define the function $F(n,p,t):=P(B>t)$. Naively, computing $F$ requires exponential (in $n$) time. ...
2
votes
1answer
116 views

Solving linear program with 1 quadratic constraint complexity

Consider the following linear program, $$\min y \\ xc_1 \leq c_2 + yz,\\ x = x_1 + \dots + x_n,\\ z \leq x_1 + x_2, \\ z \leq x_2 + x_3, \\ \vdots\\ z \leq x_{n-1} + x_n, \\ x,x_1, \dots, x_n,y,z \...
1
vote
2answers
176 views

Is Asymptotic PTAS $\subseteq$ APX?

The definition of asymptotic polynomial-time approximation scheme (Asymptotic PTAS) is defined as follows: A minimization problem $\Pi$ is Asymptotic PTAS if for all $\epsilon$ there exists an ...
1
vote
2answers
177 views

Check the match of the maximum of each subset

Given a number of vectors with $n$ elements, i.e., $S=(a_1, \cdots, a_n)$, $T_j=(b_1^j, \cdots, b_n^j)$ for $j=1,\cdots, m$ where each $a_i$ or $b^i_j$ is a natural number. Question: determine ...
22
votes
1answer
2k views

Tardos Function Counterexample to Blum's $P\neq NP$ Claim

In this thread, Norbet Blum's attempted $P \neq NP$ proof is succinctly disproved by noting that the Tardos function is a counterexample to Theorem 6. Theorem 6: Let $f \in \mathcal{B}_n$ be any ...
233
votes
11answers
115k views

Is Norbert Blum's 2017 proof that $P \ne NP$ correct?

Norbert Blum recently posted a 38-page proof that $P \ne NP$. Is it correct? Also on topic: where else (on the internet) is its correctness being discussed? Note: the focus of this question text has ...
1
vote
1answer
451 views

Clique cover problem

Consider the following graph problem. We are given a graph $\mathcal{G} = (\mathcal{V},\mathcal{E})$, where $\mathcal{V}$ is the set of vertices and $\mathcal{E}$ is the set of edges. For each vertex $...
1
vote
1answer
196 views

Max weight travel on a graph with deadline

Given a deadline $D>0$ and a complete graph $K_n$ (with loops) in which each edge $e_{ij}$ has a weight $w(e_{ij}) \ge 0$ and a travel time $l(e_{ij}) > 0$. Starting from one of the nodes, we ...
1
vote
1answer
178 views

Max-weight connected & co-connected subgraph problem

The max-weight connected subgraph problem (MWCS) may be described as follows: given a simple graph $G=(V,E)$ and a weight function $w:V\to\mathbb{R}$, one seeks for a subset $L\subseteq V$ for which ...
1
vote
1answer
192 views

Does a weighted graph have a path with weight zero?

Given a weighted digraph $G=(V,E)$, where each edge is associated with a weight (could be positive, negative, or zero). We define the weight of a path to be the sum of the weights along this path. ...
3
votes
1answer
257 views

Is deciding whether all satisfying assignments are NAE assignments coNP-complete?

Let the language $L$ consist of the $k$-CNF formulas $\phi$ with the property that any satisfying assignment $x$ of $\phi$ is a Not-All-Equal (NAE) assignment, i.e. every clause of $\phi$ has at least ...
1
vote
1answer
198 views

What is the computational complexity of this SAT Variant

Given a 3SAT problem. The question being: 'This Problem has exactly K Solutions'? Now, lets say K=1 (without loss of generality). If the problem has a exactly 1 solution and the answer is True. So, ...
-1
votes
1answer
131 views

A conceptual question regarding hardness proofs by reduction [closed]

If we restrict the input domain of a known NP-hard problem P so that this restricted domain is equal to the input domain of another problem S, then show that we can reduce a solution to P given input ...
4
votes
1answer
170 views

String version of even-odd partition problem

Motivated by Hardness proof of EVEN-ODD PARTITION post I came up with a string version. String even-odd partition INPUT: $(x_{1,0},x_{1,1}),\dots,(x_{n,0},x_{n,1})$, i.e., $n$ pairs of strings over ...
1
vote
1answer
152 views

Is pooling-aware bin packing NP-Hard?

I am unable to prove whether the following problem is NP-Hard. It seems like a bin-packing or a partition problem, without being close enough to either of them (at least I do not see the reduction to ...
6
votes
1answer
240 views

totally-mixed 2SAT with exact cardinality?

Given a 2HornSAT problem, it’s possible in linear time to find the minimum solution to the problem, i.e., a solution that minimizes the number of variables set to 1. Now let us consider the following ...
4
votes
1answer
144 views

Limits of variants of Independent Set?

Independent Set (IS) is the $\mathsf{NP}$-complete decision problem Input: graph $G$ with $v=|V(G)|$, integer $k$ Question: is there an independent set $S \subseteq V(G)$ with at least $k$ vertices? ...
5
votes
1answer
888 views

Does P = NP imply NP being a strict subset of PSPACE? [closed]

Does $\textbf{P} = \textbf {NP}$ imply that $\textbf{NP} \subsetneq \textbf{PSPACE}$? Or, for a slightly stronger result, does it imply that $\textbf{NL} = \textbf P$?
3
votes
2answers
420 views

Is this vertex ordering optimization NP-Hard?

Could you help me to prove that the following problem is NP-hard? Problem. Given an undirected graph $G=(V,E)$, find an ordering of the nodes such that $\sum\limits_{v\in V}|succ(v)|\times|pred(v)|$ ...
16
votes
2answers
414 views

Is intersection of $k \ge 3$ graphic matroids in P?

It is known that intersection of three general matroids is NP-hard (source), which is done via reduction from Hamiltonian cycle. The reduction uses one graphic matroid and two connectivity matroids. ...
6
votes
1answer
252 views

Maximum Polyhedron Volume in Given $n$ Points

Suppose we are given $n$ points $v_1,v_2,\cdots, v_n\in \mathbb{R}^k$, I want to find $k+1$ points $v_{i_1}, v_{i_2},\cdots,v_{i_{k+1}}$ such that the volume of the convex body spanned by them ...
1
vote
0answers
31 views

Sparse coding and matching pursuit algorithms

Is it true that all known sparse coding algorithms which work efficiently in practice don't have convergence proofs and always use an intermediate step of a matching/subspace pursuit algorithm on the ...
8
votes
1answer
221 views

Vertex isoperimetric number of a graph - NP-hard?

The vertex isoperimetric number of a graph $G=(V,E)$ is $i_V(G) = \min\{\frac{|N(S)|}{|S|} : S \subseteq V, 1\le |S|\le \frac{|V|}{2}\}$. Several academic papers state that the problem of computing ...
9
votes
0answers
297 views

What are the best known reductions from SAT to CNF-SAT?

Problems Let SAT denote the following problem: Given a boolean formula, does there exist a satisfying assignment? Let CNF-SAT denote the following problem: Given a ...
14
votes
2answers
521 views

Add a matching to a Hamiltonian path to reduce the max distance between given pairs of vertices

What is the complexity of the following problem? Input: $H$ a Hamiltonian path in $K_n$ $R \subseteq [n]^2$ a subset of pairs of vertices a positive integer $k$ Query: is there a matching $M$ such ...
12
votes
1answer
533 views

Are there interesting graph classes where the treewidth is hard (easy) to compute?

Treewith is an important graph parameter that indicates how close a graph is from being a tree (although not in a strict topological sense). It is well known that computing the treewidth is NP-hard. ...
12
votes
4answers
503 views

Can we fast generate perfectly uniformly mod 3 or solve NP problem?

To be honest, I don't know that much about how random number are generated (comments are welcome!) but let's assume the following theoretical model: We can get integers uniformly random from $[1,2^n]$ ...
3
votes
2answers
192 views

Hardness of finding roots of a degree $2$ polynomials over $\mathbb{F}_2$

Since every $3$-SAT instance with $n$ variables can be expressed as a degree-$3$ polynomial over $\mathbb{F}_2$ with $n$ unknowns, the NP-hardness of $3$-SAT directly translates to NP-hardness of ...