# 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
Filter by
Sorted by
Tagged with
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 ...
• 527
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; ...
• 12.8k
1 vote
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 ...
• 29
37 views

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 (...
• 29
1 vote
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 ...
211 views

393 views

• 143
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 ...
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 ...
• 445
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 ...
• 12.8k
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, ...
• 12.8k
1 vote
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 ...
• 143
1 vote
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)$, ...
• 12.8k
1 vote
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 ...
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$ ...
• 3,824