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

114
questions

-1
votes

0
answers

169
views

### If NP=P, then does quantum mechanics have a classical interpretation? [closed]

Is it true that $BQP\subset NP$, if $NP=P$?

3
votes

1
answer

365
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

5k
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)...

2
votes

0
answers

85
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

116
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

921
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

73
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

716
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

77
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

80
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

690
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

60
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

37
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

91
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

138
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

608
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

33
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

118
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 ...

12
votes

1
answer

1k
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

145
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

166
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, ...

3
votes

0
answers

121
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

173
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

47
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

40
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

117
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$ ...

14
votes

5
answers

1k
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

69
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

581
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

58
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

153
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

49
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

105
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

86
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

73
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, ...

12
votes

2
answers

407
views

### Techniques for proving relaxed one-wayness of functions

Existence of one-way functions is a widely accepted conjecture in complexity theory. A function is one-way if it is computable in polynomial-time but not invertible in polynomial-time (this is ...

15
votes

3
answers

704
views

### Representing mathematical statements as SAT instances

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

3
votes

2
answers

181
views

### (How) do Better TSP Heuristics help in Answering the $NP=P$ Question?

This question is motivated by my impression, that finding better heuristics for the TSP problem (or any other $NP$-complete problem) is "only" of practical interest, but doesn't provide any progress ...

16
votes

2
answers

553
views

### NP-hardness of finding 0-1 vector to maximize rows of {-1, +1} matrix

Consider the following discrete optimization problem: given a collection of $m$-dimensional vectors $\{ v_1, \dots, v_n \}$ with entries in $\{-1, +1\}$, find an $m$-dimensional vector $x$ with ...

1
vote

0
answers

47
views

### Cost associated set problem NP-hard

I have the following problem. I wonder whether or not it appears in the literature. Is it NP-hard?
Given a set $S = \{1,2,\ldots,m\}$, and $A_1,\ldots, A_n$ are subsets of $S$. Each set $A_i$ has ...

0
votes

1
answer

268
views

### Finding a subgraph of cliques with the minimum total sum weight

Consider the following graph problem. For a number $K$ and a set $\mathcal{K} = \{ 1, \ldots,K\}$, we have a set of vertices $V_k^s$ for all $s \subset \mathcal{K} \setminus \{k\}$, $s$ is not empty ...

3
votes

1
answer

273
views

### Simple cake cutting puzzle

I got interested in a cake cutting problem from computational perspective. Suppose we have a piece of cake and we want to slice it into pieces using several cuts (straight lines). Each cut represents ...

11
votes

3
answers

1k
views

### Is there a polynomial-time algorithm for untangling the unknot?

I've found assertions that recognising the unknot is NP (but not explicitly NP hard or NP complete). I've found hints that people are looking for untangling algorithms that run in polynomial time (...

0
votes

1
answer

120
views

### Continuous backpack with multiple choice items. NP prove

Continuous backpack with multiple choice items is the problem where you need to collect items by one from each of distinct sets and associate them with rational numbers so that their sum of weights ...

4
votes

1
answer

797
views

### What arguments do exist against defining completeness in NP using injective Karp reductions?

It is crucial to use the right notion of reduction to define completeness inside NP. Different notions of completeness inside NP may have significant impact on the properties of complete languages. ...

7
votes

3
answers

1k
views

### How slow are direct solutions of NP-complete problems on computers?

Sometimes I see that people call a problem NP-hard and because of that refuse to create computer algorithms that directly solve it. I think I've never read actual benchmark results for such problems. ...

3
votes

1
answer

132
views

### Covering a graph by trees with depth constraint

Given a graph $G$ and a depth constraint $h$, my question is: what is the complexity to find a tree cover of $G$, denoted as $T=\{T_1, T_2, ..., T_n\}$. For each $T_i$, its depth(height) is no larger ...

2
votes

1
answer

106
views

### Minimum cover for sets in which each element appears in exactly 2 sets?

Is there an algorithm for finding minimal covers of a set of sets in which each element of the universe appears in exactly 2 sets? I realize that LP relaxation approximates this to within a factor of ...

1
vote

0
answers

161
views

### How I can prove the equality $P^{P_{\operatorname{space}}}=NP^{P_{\operatorname{space}}}=P_{\operatorname{space}}^{P_{\operatorname{space}}}$ [closed]

I know how to prove that if $A \in P^{P_{\operatorname{space}}}$ then $A \in NP^{P_{\operatorname{space}}}$ and $A \in P_{\operatorname{space}}^{P_{\operatorname{space}}}$.
I don't know how to prove ...

2
votes

2
answers

412
views

### How to complete the NP-hardness proof of GENERAL-SQUARE-PRODUCT?

I am interested in the complexity of the following problem:
GENERAL-SQUARE-PRODUCT
INSTANCE: Two sets $A=\{a_1,\ldots,a_n\}$ and $B=\{b_1,\ldots,b_n\}$ of integers, a positive integer $k<n$ and a ...