# 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 '.

127 questions
Filter by
Sorted by
Tagged with
1 vote
37 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 ...
63 views

210 views

106 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 ...
217 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 ...
20 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 ...
60 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
66 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
52 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
106 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 ...
733 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$ ...
6k views

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 304 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 162 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 ... 8 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 102 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 771 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 110 views ###$W$-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$-hard when parameterized by treewidth. However, ... 0 votes 1 answer 115 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 727 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 64 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 41 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 97 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 ... 0 votes 0 answers 180 views ### Computational practicality of proving a theorem by transforming into a map coloring and finding$P(3)$, where$P$is the chromatic polynomial So I have heard that you can transform a math statement into a map in such a way that proving the statement is true is equivalent to finding a$3$-coloring of that map. I'm also aware that you can ... 3 votes 1 answer 917 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 136 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 ... 13 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 178 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 158 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 193 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 52 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 120 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$... 18 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 82 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 653 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 62 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 186 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? 3 votes 0 answers 54 views ### Karp hardness of two cycles which lengths differ by one Our problem is as follows: NEARLY-EQUAL-CYCLE-PAIR Input: An undirected graph$G(V,E)$Output: YES if there exists$2$(simple) cycles in$G$which lengths differ by$1$, otherwise NO Is it$NP$-... 3 votes 0 answers 130 views ###$\mathrm{NP}$-complete problems in graph theory: undirected vs. directed Is it true that it is much easier to establish$\mathrm{NP}$-complete on undirected graphs than digraphs (directed graph)? Academic articles proving$\mathrm{NP}$-completeness of problems on ... 1 vote 0 answers 96 views ### descriptive complexity theory to attack computational complexity problems [closed] What is the usefulness of descriptive complexity to attack computational complexity theory?what are the recent results in this direction? Thanks 1 vote 0 answers 75 views ### Bipartite clustering is NP-hard? Let$G = (A\cup B, E)$be a bipartite graph with edge weights$w: E\to \mathbb{R}$. Find a partition$B_1, B_2$of$B$and a nonempty disjoint subsets$A_1, A_2$of$A$such that$w(A_1,B_1) + w(A_2, ...
The following problem (call it THEOREMS) belongs to class NP. Input: Mathematical statement $S$ (written in some formal system such as ZFC) and positive integer $n$ written in unary. Output: "Yes" if ...