# Questions tagged [np]

In computational complexity, NP is the complexity class consisting of problems whose yes instances can be verified in polynomial time. NP stands for 'nondeterministic polynomial time '.

133
questions

0
votes

1
answer

153
views

### How to determine if a set is a sumset

Let $G$ be a commutative group (assume whatever you want on $G$ if needed. I am mainly interested in $G = \mathbb{Z}/n\mathbb{Z}$).
Let $k$ be a fixed integer.
Let $(a_1, \dots, a_{k^2})$ be a list of ...

0
votes

0
answers

17
views

### Any updates on "The minimum cost perfect matching problem with conflict pair constraints"?

The subject of the paywalled article The minimum cost perfect matching problem with conflict pair constraints (MCPMPC) are perfect matchings of minimum cost that do not contain certain pairs of edges; ...

1
vote

0
answers

92
views

### Quasi polynomial algorithm for NP complete problem [closed]

I know that quasi polynomial algorithm is neither polynomial nor exponential. But I want to know if we find such algorithm for NP complete problem, will it be of any use? Or is there such algorithm ...

0
votes

0
answers

37
views

### Prove the NP-hardness of the following problem: Whether there exists a partition for a set of data points

Can anybody help me prove the NP-hardness of the following question:
Given $x_0, x_1, ..., x_m \in \mathbb{R}^n$, determine whether there exists a partition $S\cup [m]\backslash S$, such that $x_0 \in ...

3
votes

0
answers

248
views

### Is there a version of 3-SAT that is NP-complete but grows like $2^n$ instead of $2^{n \choose 3}$?

If I have $n$ variables and I want to write down all 3-SAT problems, the number of problems is $2^{8{n \choose 3}}$, since each clause has 3 variables and each variable can be negated or not.
But ...

0
votes

0
answers

14
views

### Complexity of finding single source paths with capacity constraints and length constraints

Let $G=(V,A)$ be a directed graph with distinguished vertex $s\in V$ and let $c:A\rightarrow{\mathbb N}$ denote arc capacities. For any $t\in V,t\not=s$ we are given two numbers: $C_{t},L_{t}$. Let $...

0
votes

0
answers

29
views

### The hardness of active learning with fixed budget

I have been looking for theoretical papers studying this question of the fundamental hardness of PAC active learning algorithms. I found a few papers studying the problem from a fixed perspective (...

1
vote

0
answers

51
views

### Hardness of an optimization problem when some variables are fixed

Given a general optimization problem, I would like to know what we can say about the hardness of the problem when a subset of its variables are fixed.
With the two (related) examples, it is clear that ...

2
votes

1
answer

211
views

### Can we say this nonlinear integer programming problem is NP-hard?

I was wondering if the following nonlinear integer programming problem is NP-hard or not.
$$\max_{x_i \in \{0,1\}} \frac{\sum_{i=1}^{n}a_i x_i}{\sqrt{\sum_{i=1}^{n}b_i x_i}}$$
such that $\sum_{i=1}^{n}...

2
votes

2
answers

962
views

### Using Kolmogorov complexity to measure difficulty of problems?

We call the natural number $n$ a partition number $\iff$
$$
\exists d | n: \gcd\left(d,\frac{n}{d}\right)=1 \text{ and } \Omega(d) = \Omega\left(\frac{n}{d}\right)\;,
$$
where $\Omega$ counts the ...

2
votes

2
answers

207
views

### Is it NP-hard to find the min set of nodes in a graph so that the set of paths joining them cover all the nodes?

Given a directed graph $G=(V,A)$ and given for every pair of nodes $(i,j)$
a valid path $P(i,j)=(v_1=i,...,v_l=j)$ on $G$.
Find a minimum set of nodes $M$ such that $\bigcup_{(i,j)\in M\times M}P(i,j)=...

2
votes

1
answer

393
views

### Modular square roots problem which is $NP$ hard

It is well known extracting modular square roots modulo a composite number factors the modulus.
On other hand given $u,v>0$ and an integer $n$, deciding if there is a factor of $n$ in $[u,v]$ is $...

1
vote

1
answer

53
views

### Path cover with sets of nodes

I am considering the following variant of the path-cover problem. I have an acyclic directed graph G=(V,E). Moreover, the set V is partitioned into $V=V_1 \cup ... \cup V_k$ (these sets are pairwise ...

0
votes

2
answers

225
views

### Compute the average path weights of paths with the same path length in a directed acyclic graph (DAG)

Given a weighted directed acyclic graph (DAG) $G=(V,E)$ with each edge $e\in E$ has a non-negative weight $w(e)$. For a path $p=(e_1,e_2,\dotsc,e_n)$ in $G$, define the path weight as : $w(p)=\sum_{i=...

0
votes

1
answer

115
views

### Traveling salesperson problem algorithm [closed]

I was wondering something, let's say in a symmetric distance matrix of a sample of TSP, there was a sure algorithm that could remove between 30% to 80% of the values (distances) that wouldn't ...

5
votes

2
answers

273
views

### Is it still not known whether the construction of shortest nonzero vector of a lattice w.r.t. $l^2$-norm is NP-hard?

It was shown in
P. van Emde Boas, Another NP-complete partition problem and the complexity of computing short
vectors in a lattice
that the construction of a shortest nonzero vector of a Euclidean ...

0
votes

0
answers

21
views

### Complexity of reporting solutions to a decision problems

Suppose we have an oracle that tells us whether an instance of the Hamilton cycle problem contains a Hamilton cycle or not.
Question:
what is the complexity of e.g. finding the edges constituting to a ...

0
votes

0
answers

65
views

### Validity of an argument for an implication of NP-Completeness

Fedor Petrov has posed a notorious problem regarding the existence of a matching in this question: Resolution of multiple edges
As I see it the setting is a constrained bipartite matching and thus, ...

1
vote

0
answers

72
views

### cut a path from DAG that has minimal conductance

Given a directed acyclic graph $G=(V,E)$, a source node $s$ and a sink node $t$, we want to find a path $P$ from $s$ to $t$ such that if we separate all the nodes in $V$ to two parts $P$ (all the ...

1
vote

0
answers

55
views

### What is an approximation algorithm in the context of NP completeness in general

In theorem 4 of Approximability of Minimum-weight Cycle Covers Bodo Manthey proves that:
Then no approximation algorithm
for $\operatorname{Min-L-DCC}$ achieves an approximation ratio of $o(n)$, ...

1
vote

1
answer

114
views

### Problem NP-completeness on a specific graph class

Consider the class of simple connected n/2-regular graphs, n even. Are the maximum clique problem and/or maximum independent set problem NP-complete on such graphs? Is there any known result which ...

3
votes

1
answer

987
views

### Root of polynomials in a finite field

I am looking for a way to find out if a polynomial $P\in \mathbb Z/p\mathbb Z=\mathbb F_p$, of great degree, has roots in $\mathbb F_p$, with $p$ a big prime number.
For example : $p=2^{2020}-69$ ...

22
votes

2
answers

6k
views

### $\mathbf{P} = \mathbf{NP}$, what's the problem?

Let's take the problem of the backpack: $A_1,\ldots ,A_n$ the weights that are integers, and we want to know if we can achieve a total weight of $V$.
We take $$I=\dfrac{1}{2\pi}\int_0^{2\pi} \exp(-iVt)...

4
votes

1
answer

348
views

### Lower bound on the number of solutions of 2SAT

To compute the number of solutions of a 2SAT is a hard problem. Is there some nontrivial lower or upper bound on this number in terms of a “coarse-grained” description of the Boolean formula, for ...

1
vote

1
answer

180
views

### Boolean function : approximation by a linear function

Let $f$ be a balanced Boolean function.
Are there $g$ linear functions, with $$\frac1{2^n}\mathrm{card} \big(\big\{\mathrm{sign} (g (x)) = 2f (x) -1, x \in \{0,1\}^n\big\}\big) > 0.55\quad ?$$
$g ...

10
votes

3
answers

1k
views

### Is there a website or a survey collecting all NP-complete problems on graph theory?

I wonder whether there is a website or a survey collecting all known NP-complete or NP-hard problems on graph theory?

0
votes

0
answers

125
views

### What does it mean to find an efficient algorithm for NP complete problems

Suppose I have a problem $P$, an instance $I$ and an algorithm $A$ that efficently solves $P$ for $I$.
Let $P'$ be $P$ with additional constraints that are violated if $A$ is applied to $I$ and ...

13
votes

3
answers

823
views

### Undecidable infinite analogs of NP-complete problems?

In the paper Some undecidable problems involving edge-coloring of graphs, Burr proves that a certain k-coloring problems for certain infinite graphs (however, with finite descriptions - here "...

2
votes

1
answer

114
views

### $W[1]$-hard and FPT about the equitable tree-coloring problem

I am confused by the two conclusions in this paper (DOI link behind paywall at Springerlink).
It shows that the equitable tree-coloring problem is $W[1]$-hard when parameterized
by treewidth.
However, ...

0
votes

1
answer

136
views

### Is minimum weight vertex cover problem NP-easy? [closed]

I think that Minimum weight vertex cover problem is NP-easy. However I don't know how to prove that. Does anyone know how to prove it?

7
votes

1
answer

756
views

### $\mathit{NP}$-hard statements which are $\mathit{NP}$-complete under the Riemann Hypothesis

$\newcommand\NP{\mathit{NP}}\newcommand\SAT{\mathit{SAT}}\newcommand\CH{\mathit{CH}}\newcommand\PSPACE{\mathit{PSPACE}}$Are there $\NP$-hard problems which are $\NP$-complete under the Riemann ...

1
vote

0
answers

69
views

### Subgraph isomorphism problem with linear map

I am working on proving the NP-hardness of a problem by reducing it from the subgraph isomorphism problem. Currently, I can reduce it from the following problem:
Problem 1: Given two graphs $G=(V, E)$ ...

1
vote

0
answers

45
views

### Computational complexity of rate $\frac{1}{2}$ codes

We know from Berlekamp, McEliece and Van Tilborg [On the inherent intractability of certain coding problems, IEEE Trans. Information Theory, 24 (1978)] that computing the minimum distance of a (binary)...

1
vote

0
answers

107
views

### Promise version of minimum distance

It has been known for some time that computing minimum distance of a linear code (minimum weight codeword) is NP-hard.
This immediately also says that given a code $C$, calculating minimum hamming ...

3
votes

1
answer

1k
views

### Is there an example of converting a mathematical statement into a three color mapping? [closed]

https://youtu.be/5ovdoxnfFVc?t=1118
At this point, prof Wigderson says it is easy to go from a mathematical statement to a graph coloring problem. The video does not provide an example of this, and a ...

1
vote

0
answers

37
views

### Finding valuable conjectures from NP-Complete problems [closed]

Let's suppose we've got an NP-Complete problem, such as the subset sum problem. There are conjectures that, if proven true, would place the subset sum problem to the P-Complete problem realm?
If the ...

-1
votes

3
answers

156
views

### Are <sum, product, N> triplets unique and hard to solve? [closed]

This question comes from some reasoning I made myself about a "joke block chain" where every new block is labeled with a triplet <S, P, N> where where S = sum of the N transactions so ...

15
votes

2
answers

2k
views

### How did the Baker-Gill-Solovay paper come to be?

How did the Baker-Gill-Solovay paper come to be? Why were those three people talking together about "Relativizations of the $P=?NP$" question, and what was their collaboration like for the ...

2
votes

2
answers

156
views

### Transforming an optimization problem to maxmin formulation

Given $N=mn$ real numbers $a_i$, we seek to partition them into $n$ subsets $S_j$ ($1\le j\le n$), each containing $m$ numbers, so as to maximize $\prod_{j=1}^n \sum_{a_i\in S_j} a_i$. My questions ...

2
votes

1
answer

184
views

### What is the efficiency of this algorithm which decides the answer to the Boolean satisfiability problem? [closed]

I have just written a short javascript program which, given any boolean expression with $N$ variables, completes in N "ticks" of the clock and which makes the decision. I will explain this algorithm, ...

4
votes

0
answers

184
views

### Is the Weber problem a NP-hard problem?

The Weber problem is a special case of a facilities location problem : In a basic formulation, the facility location problem consists of a set of potential facility sites L where a facility can be ...

0
votes

1
answer

205
views

### Is it theoretically possible to find a factoring algorithm that runs in polynomial time? [closed]

Given that we don't know if P=NP, what's to stop someone from finding tomorrow an algorithm that makes prime factoring, or any other trap-door function reversing for that matter, computationally ...

2
votes

0
answers

56
views

### Proof for the NP-hardness of the Max-3-DCC Problem

The Max-3-DCC is the variant of vertex cycle cover problem where each of the vertex disjoint oriented cycles consists of at least 3 arcs and every vertex belongs to exactly one of those cycles; ...

1
vote

0
answers

43
views

### Determining the minimum weight maximal oriented subgraph of a complete directed graph

Let $G(V,A,W):\ |V| = n,\ A=V\times V\setminus \lbrace (v,\ v)\rbrace,\ W\in\mathbb{R}_+^{n\times n},\ W^T\ne W $ be a complete directed graph with asymmetric weights.
Questions:
What is the ...

1
vote

0
answers

122
views

### Is bounded graph isomorphism $NP$ complete?

Fix a matrix $M\in(\mathbb Z\backslash\{0\})^{n\times n}$ where $\|M\|_\infty\leq 2^{poly(n)}$.
Is the bounded graph isomorphism problem
Given symmetric $A,B\in\{0,1\}^{n\times n}$ and $U,V>0$ ...

19
votes

5
answers

2k
views

### Equivalent forms of the P vs. NP problem

Many things in math can be formulated quite differently; see the list of statements equivalent to RH here, for example, with RH formulated as a bound on lcm of consecutive integers, as an integral ...

2
votes

0
answers

87
views

### NP - hardness of school scheduling problem with a restriction

I do have a real-life scheduling problem for a special education school.
Basically, i have a binary variable containing teachers, subject, time slot and rooms as indices.
The goal is to assign each ...

16
votes

2
answers

701
views

### Is this kind of "Gerrymandering" NP-complete?

[I posted this on Math Stack Exchange about two weeks ago, but didn't get any reply, so I'm trying it here.]
Consider the following simplified form of "Gerrymandering": You have $n^2$ ...

1
vote

0
answers

68
views

### Shortest Lattice Vector with restricted $x$

Let $\Lambda$ be a lattice with basis, $B$ consisting of vectors $b_i$, so that the elements of $\Lambda$ are of form, $y\in \Lambda \iff y=Bx=\sum_i b_ix_i$ for some $x_i\in\mathbb{Z}$.
My questions ...

1
vote

0
answers

196
views

### Is it known whether $\mathrm{NP \subseteq P/poly}$?

It is not immediately clear to me whether this statement is true or false. Can finite restrictions of NP problems be computed in polynomial time?