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

Filter by
Sorted by
Tagged with
0 votes
0 answers
21 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 ...
Robeto Leo's user avatar
2 votes
0 answers
200 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 ...
Logan 's user avatar
  • 21
0 votes
0 answers
13 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 $...
Yossi Peretz's user avatar
0 votes
0 answers
26 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 (...
rivana's user avatar
  • 29
1 vote
0 answers
47 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 ...
Ro. Cohof's user avatar
2 votes
1 answer
146 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}...
Anson's user avatar
  • 21
2 votes
2 answers
937 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 ...
mathoverflowUser's user avatar
2 votes
2 answers
201 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)=...
user3020699's user avatar
2 votes
1 answer
296 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 $...
Turbo's user avatar
  • 13.6k
1 vote
0 answers
25 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 ...
Andres Fielbaum's user avatar
0 votes
2 answers
190 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=...
cbyh's user avatar
  • 143
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 ...
Ehsan Javanbakht's user avatar
5 votes
2 answers
239 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 ...
taylor's user avatar
  • 425
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 ...
Manfred Weis's user avatar
  • 12.6k
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, ...
Manfred Weis's user avatar
  • 12.6k
1 vote
0 answers
71 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 ...
cbyh's user avatar
  • 143
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)$, ...
Manfred Weis's user avatar
  • 12.6k
1 vote
1 answer
113 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 ...
Valentin Brimkov's user avatar
3 votes
1 answer
874 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$ ...
Dattier's user avatar
  • 3,737
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)...
Dattier's user avatar
  • 3,737
4 votes
1 answer
339 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 ...
Alm's user avatar
  • 1,159
1 vote
1 answer
171 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 ...
Dattier's user avatar
  • 3,737
9 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?
W. Paul Liu's user avatar
0 votes
0 answers
119 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 ...
Manfred Weis's user avatar
  • 12.6k
13 votes
3 answers
804 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
111 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, ...
Zhukui Bai's user avatar
0 votes
1 answer
128 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?
Zhukui Bai's user avatar
7 votes
1 answer
742 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 ...
Turbo's user avatar
  • 13.6k
1 vote
0 answers
65 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)$ ...
lisi's user avatar
  • 101
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)...
Root's user avatar
  • 71
1 vote
0 answers
101 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 ...
Root's user avatar
  • 71
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 ...
Abhishek cherath's user avatar
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 ...
Martí Llopart's user avatar
-1 votes
3 answers
150 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 ...
Carlo Moretti's user avatar
14 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 ...
user avatar
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 ...
lchen's user avatar
  • 459
2 votes
1 answer
180 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, ...
user avatar
4 votes
0 answers
175 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 ...
Julien's user avatar
  • 141
0 votes
1 answer
197 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 ...
c3200015's user avatar
2 votes
0 answers
53 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; ...
Manfred Weis's user avatar
  • 12.6k
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 ...
Manfred Weis's user avatar
  • 12.6k
1 vote
0 answers
121 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$ ...
Turbo's user avatar
  • 13.6k
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 ...
Michael's user avatar
  • 2,155
2 votes
0 answers
86 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 ...
momo's user avatar
  • 21
16 votes
2 answers
686 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$ ...
Frunobulax's user avatar
1 vote
0 answers
65 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 ...
hookah's user avatar
  • 1,096
1 vote
0 answers
195 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?
user131392's user avatar
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$-...
T. D. Nguyen's user avatar
3 votes
0 answers
145 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 ...
user avatar
1 vote
0 answers
100 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
Hao  Yu's user avatar
  • 11