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
1
vote
0
answers
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 ...
- 11
2
votes
0
answers
63
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}...
- 21
2
votes
2
answers
889
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 ...
- 1,866
2
votes
2
answers
174
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)=...
- 21
2
votes
1
answer
210
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 $...
- 13.5k
1
vote
0
answers
19
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
129
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=...
- 143
0
votes
1
answer
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 ...
5
votes
2
answers
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 ...
- 425
0
votes
0
answers
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 ...
- 12.3k
0
votes
0
answers
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, ...
- 12.3k
1
vote
0
answers
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 ...
- 143
1
vote
0
answers
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)$, ...
- 12.3k
1
vote
1
answer
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 ...
- 105
3
votes
1
answer
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$ ...
- 3,561
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)...
- 3,561
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,149
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 ...
- 3,561
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?
- 493
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 ...
- 12.3k
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[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, ...
- 59
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?
- 59
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 ...
- 13.5k
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)$ ...
- 101
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)...
- 71
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 ...
- 71
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 ...
- 101
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 ...
- 109
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 ...
user44143
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 ...
- 459
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, ...
user49545
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 ...
- 141
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 ...
- 1
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; ...
- 12.3k
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 ...
- 12.3k
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$ ...
- 13.5k
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,145
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 ...
- 21
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$ ...
- 263
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,096
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?
- 11
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$-...
- 121
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 ...
user128192
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
- 11
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, ...
- 221
12
votes
2
answers
420
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 ...
- 2,881
16
votes
4
answers
864
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 ...
- 771