Questions tagged [np-complete]
Questions on the topic of NP-Completeness, which comes from Theoretical Computer Science
659
questions
6
votes
2
answers
255
views
Distributing marbles into buckets for maximal colour sharing
i've got a problem that feels very much like it's NP-hard but I would love some help proving it primarily.
Secondary to that, if an optimal polynomal time algorithm can be proposed that is even better,...
- 121
1
vote
0
answers
29
views
Why finding the shortest solution for a linear Diophantine equation is a NP problem?
I read this paper saying: ...finding the shortest solution for a linear Diophantine equation is a NP problem?
I have two questions:
1). What it means of "the shortest solution" for linear ...
- 107
1
vote
0
answers
30
views
When we necessarily need monadic second order logic
I am a student of graph theory and recently started learning mathematical logic.
If I am not wrong, any problem in the class Np-Complete can be represented as a SAT formula. As boolean formulas are a ...
- 21
0
votes
0
answers
21
views
shortest vector problem with lattice using Euclidean $L^2$ norm
I'm wondering about the time complexity for the closest vector problem and the shortest vector problem with a twist:
This is the statement for the SVP I wish to consider:
$$\lambda(H) = \min_{v \in H- ...
- 850
0
votes
0
answers
50
views
Is this discrete optimization problem NP-complete?
Consider a finite set $A \subseteq \mathbb{N} \times \mathbb{N} \times \mathbb{R}$.
Minimize
$$\sum_n \left( \max_{(n',i,a) \in A, n=n'} (a + x_i) + \max_{(n',i,a) \in A, n=n'} (-a - x_i) \right)$$
...
-1
votes
1
answer
43
views
non primitive recursive algorithms having polynomial time verification? [closed]
i think the title speaks for itself,
since the defining trait for NP class is that - they are the set of decision problems verifiable in polynomial time by a deterministic Turing machine.
thus it ...
- 7
3
votes
0
answers
29
views
Is Linear Separability of a binary dataset NP-hard?
The Question
Is the following problem P or NP?
Given a binary datast $\left\{ \left(x_{i},y_{i}\right)\right\} _{i=1}^{\mathcal{O}\left(n\right)},\;x_{i}\in\left\{ -1,1\right\} ^{n},\;y_{i}\in\left\{ ...
- 411
1
vote
0
answers
29
views
P versus NP and the Irreducibility of NP-Complete Problems to P-Complete Problems
If it can be shown that a given NP-complete problem such as Clique cannot be reduced to a given P-complete problem, such as Horn-SAT, then we can conclude that P does not equal NP?
- 1,680
1
vote
0
answers
11
views
Is Maximizing utility with compliment/substitutes NP
I was trying to code a simple economics simulator where consumers try and maximize their utilities based on a lot of parameters and I think that maximizing utilities is NP-hard but I wanted to ask you ...
- 11
0
votes
0
answers
10
views
Prove that the language HAMTWOCYCLES = {G | there exist two cycles in G such that any vertex belongs to exactly one of them} is NP-complete
I have attempted to prove this theorem, but I am not confident in my solution. Can someone please review my proof and let me know if there are any errors, or provide a correct proof if mine is ...
- 7
0
votes
0
answers
20
views
Construct NP-complete languages A and B such that A ∪ B = {0, 1}*
I have attempted to prove this problem, but I am not confident in my solution. Can someone please review my proof and let me know if there are any errors, or provide a correct proof if mine is ...
- 7
3
votes
1
answer
130
views
Take a 3-SAT system and compute its symmetry group, what can we say? How does this group relate to satisfiability?
Take for example, the $3$-CNF system:
$$
a \vee b \vee c = 1 \\
d\vee -e \vee f = 1
$$
The symmetry group of the first equation is $S_3 = \langle (x,y) : x, y \in \{a,b,c\}, x\neq y \rangle$ because ...
- 20.8k
0
votes
0
answers
18
views
Reducing Hamiltonian path to TREFOIL
HAMTREFOIL = {(G,s,t,u,v) | there exist paths s->t, s->u, s->v such that every vertex(except s) belongs to one of the paths}
I want to prove that HAMTREFIOL is NP-complete by reducing ...
0
votes
0
answers
19
views
How can I reduce 3-SAT NAE to Set Partition?
I need to reduce Partition of a Set from 3-SAT NAE to prove that set partitioning is NP-Complete.
I have this:
Given an instance of NAE-3-SAT, the reduction builds an instance of the set partition ...
0
votes
0
answers
38
views
Optimization Partition Problem can be solved in polynomial time if the decision partition can be solved in polynomial time
the decision partition problem is Np-complete.Now I would like to proof that if a polynomial Algorithm exists for the decision Problem than another polynomial algorithm would exist too, that would ...
- 1
-1
votes
1
answer
35
views
Is the following Knapsack Variant NP-Hard?
The problem: Let $A_1 = \{a^1_1,\ldots,a^1_n\}, A_2 = \{a^2_1,\ldots,a^2_n\}, \ldots, A_k = \{a^k_1,\ldots,a^k_n\} \subset \mathbb{N}$ be $k$ sets of $n$ integers, and let $U,L \in \mathbb{N}$ be ...
- 63
0
votes
0
answers
43
views
P and NP Questions
I have 2 questions.
(1) Assume problem B is NP-complete and it is polynomial time reducible to problem A. Also the problem A is polynomial time reducible to problem B. Then is A NP-complete?
We ...
- 85
0
votes
1
answer
40
views
complexity classes NP vs. BPP and similar
I do not understand well the relation between nondeterministic class $\mathsf{NP}$ and a probabilistic one, say $\mathsf{BPP}$. Both uses some guesses and random decisions.What is the most direct ...
- 3,802
6
votes
0
answers
355
views
Is the problem NP-hard?
Let $GF(p) = ({\mathbb Z}_p, +, \times)$ be the Galois field where $p>2$ is prime and let
$$
H=\{1,2,\cdots, \frac{p-1}{2}\}.$$
I need an algorithm (subexponential in terms of $\log_2 p$) that ...
- 381
1
vote
1
answer
49
views
Polynomial time approximation methods for TSP
I am aware that the Christofides algorithm is the best known polynomial-time algorithm for approximating solutions to the traveling salesman problem, but it only works for the metric TSP. Does anyone ...
- 72
0
votes
0
answers
53
views
Reduction for NP complete proof
Consider the problem “wellMath”, which is defined as follows:
{
Input: An undirected graph G = (V, E) and a positive integer p.
G contains a well-separated matching of size p.
}
"We define a well-...
2
votes
1
answer
47
views
Is there a theorem that states that Integer Linear Problems with a Totally Unimodular constraint matrix are solvable in polynomial time?
Is there a theorem that states that Integer Linear Problems with a Totally Unimodular constraint matrix are solvable in polynomial time?
If the answer is positive, is it also valid for Mixed-Integer ...
- 39
0
votes
0
answers
51
views
Give 1-approximation algorithm $Z-Tree$
$G$ = ($V$,$E$) is a complete graph, $X$ is a subset of $V$, and every edge satisfies the triangle inequality property. $X$-spanning tree is a sub-graph of $G$ that is a tree whose vertex set is ...
- 33
0
votes
0
answers
27
views
Subset sum problem with fixed linear constraints
I am currently troubled by a problem that seems to be a generalization of the NP-hard subset sum problem over a finite field $\mathbb{F}$. For simplicity, let's assume $\mathbb{F}$ is of a large prime ...
- 131
2
votes
1
answer
31
views
Is One Way TSP NP-complete?
I know that One Way TSP (TSP but the salesman does not have to return to his original city) is NP-Hard, but is it NP-Complete? I ask this because I recently found a solution to Open TSP but can't find ...
- 227
1
vote
1
answer
59
views
Conditional constraints in Integer Linear Programming
I think it's rather a simple question. I'm trying to construct a reduction from graph problem to ILP. When I have variables $x_1, x_2, \dots ,x_n \in \{0, 1\}$ for every vertex, can I create ...
- 37
1
vote
0
answers
27
views
Proving the language 2-SIMPLE-PATH is in NL
The Question
I define the language$$\mathsf{2-SIMPLE-PATH}=\left\{ \left\langle G,s,t\right\rangle \left|\begin{array}{c}
\mathsf{there\;are\;two\;different}\\
\mathsf{simple\;paths\;from}\;s\;\...
- 249
6
votes
2
answers
408
views
What does "NP-hard to distinguish ... between ... and ..." mean?
I am reading paper Hardness Results for Weaver’s Discrepancy Problem. In the abstract, the paper reads
it is NP-hard to distinguish such a list of vectors for which there is a signed sum that equals ...
- 705
0
votes
0
answers
56
views
Is convex program with exponential constraints NP-Hard
Convex optimization is widely known to be solvable in polynomial time, but is it still true when a convex program has an exponential number of constraints? For example, I have a convex program as ...
- 127
0
votes
1
answer
31
views
All graphs that are subgraphs of a fixed Graph $G$ is in $P$ or in NPC?
I'm studying for my computation exam and came across the following question:
Given a Graph $G=(V_G,E_G)$,
$G$ contains a copy of $H=(V_H,E_H)$ if there exists a subgroup of $S\subseteq$$V_G$ of size |$...
- 141
1
vote
0
answers
37
views
Understanding Reduction Problem
I am having troubles understanding the concept of reduction and its relation with complexity.
I have defined some problems as follows:
BreakRSA: From $(n = pq, e)$ find $d$ such that $ed = 1 \mod φ(n)...
1
vote
2
answers
81
views
Proving BinPacking is NP-complete given Partition problem is NP-hard
I'm trying to prove that the BinPacking problem is NP hard granted the partition problem is NP hard. If I have E a set of positive integers, can I split it into two subsets such that the sums of the ...
0
votes
1
answer
108
views
Proof of NP-completeness of the 3-SAT problem
Proposition : The 3-satisfiability problem 3-SAT is NP-complete.
Proof : We give a polynomial-time reduction of SAT to 3-SAT. Let $f(x_1, x_2,\ldots)$ be a Boolean expression. Introduce a variable $...
- 1,208
2
votes
0
answers
89
views
Can protein folding be used to solve SAT problems?
Given a sequence of amino acids, the protein folding problem is to find a geometric structure of the amino acids that minimizes energy. Given that this problem is NP-Hard, one should be able to do the ...
- 61
2
votes
1
answer
124
views
Vertex coloring approximation algorithm using linear programming
The vertex coloring of an undirected graph $G = (V,E)$ is to assign as few colors as possible to each node such that adjacent node has different colors. I know that this problem can be represented as ...
- 301
0
votes
0
answers
28
views
How to give a zero-knowledge proof for G3C being NP-complete
I watched a YouTube video where Avi Wigderson explained his work on zero-knowledge proof. He mentioned that all mathematical statement that has a proof has a Zero-Knowledge Proof.
I also read the ...
-1
votes
1
answer
78
views
Is the problem of the form $ax=b \pmod{n}$, where $\gcd(a,n)\ne 1$, an NP-complete problem? [duplicate]
I am working with polynomials defined over the ring $\mathbb{Z}/n\mathbb{Z}$ of the form $$a_ix_i = A_i\pmod{n},$$ where $\gcd(a_i,n) \ne 1,$ for all $i \in \{0, \dots, k\}$, $n$ is a composite number....
- 165
1
vote
0
answers
57
views
Would a runtime of (n choose (n/2)) be considered polynomial?
Simple question, given an input of size n, would an algorithm with runtime O(n choose (n/2)) = n!/((n/2)!(n/2)!), a.k.a. an algorithm which evaluates every possible partitioning of the input into two ...
- 11
0
votes
1
answer
56
views
A version of an algorithm for an "uniform" subset sum problem?
Let $l_1,\cdots,l_n \sim U(0,1)$ be i.i.d uniform variables. Given $L>0$ a natural number, let us define the "uniform" subset sum problem as:
Find $I \subset \{1,\cdots,n\}=:[n]$ such ...
- 595
4
votes
0
answers
194
views
Does a cubic graph polynomial contain the $x_1 x_2 \cdots x_M$ term?
Given a cubic graph $G$ (i.e. a graph where all nodes have degree $3$) with $N$ nodes and $M$ edges, each edge is assigned a variable $x_i$. For each node, we are given $y_i$ which is a polynomial in ...
- 1,762
0
votes
1
answer
40
views
Finding independent set in a cubic graph
This question is a reference request. I am pretty sure that finding an independent set of size at least $k$ in $G$, where $G$ is a cubic graph, is an NP-hard problem. However, I did not find any ...
- 243
0
votes
1
answer
53
views
Is the Generalized Assignment Problem with weights=1 NP-hard?
Description
The Generalized Assignment Problem consists into assigning an items $i$ to a bins $j$.
If we assign item $i$ to bin $j$ (i.e., $x_{ij}=1$) we obtain a profit $p_{ij}$.
Each bin $i$ has its ...
0
votes
1
answer
111
views
Travelling Salesman Problem
I am a bit confused with the following: We know that if P = NP then the TSP problem can be solved in polynomial time, whereas if P != NP there is no polynomial time approximation algorithm.
The ...
- 11
3
votes
0
answers
44
views
Minimum spanning forest, for a complete graph.
Given a complete Graph $G(V,E)$ with $|V|=kn$ and weights $w:E→N$ that satisfies "Triangular Inequality". That is, for any $v_1, v_2, v_3 \in V$,$$w(v_1,v_2)\le w(v_1,v_3)+w(v_3,v_2).$$
Can ...
- 71
2
votes
0
answers
73
views
Variation on the minimum clique cover problem (NP Hard)
I have a variation of the NP-hard minimum clique cover problem. My problem reduces to that problem, so is also NP-hard.
We have $n$ sets of vertices. Each set has between $1$ and $k$ vertices. Let's ...
- 306
1
vote
1
answer
65
views
Time Complexity and Polynomial Reduction
Let $A$ be an NP- complete problem, if there is an algorithm that solve $A$ in $2^{o(n)}$, does this means that $NP \not= ExpTime$ ? if this is true then i have a follow up question.
Let $A,B$ be 2 NP ...
- 1,948
4
votes
1
answer
68
views
Minimum spanning forest, where each tree has the same number of vertices.
Given a connected Graph $G(V,E)$ with weights $w\colon E\to\mathbb{N}$ and $|V|=kn$. How can I find the minimum spanning forest $T_1,T_2, \dots, T_n$ where each tree $T_i$ has exactly $k$ vertices?
I ...
- 71
1
vote
0
answers
23
views
Special graphs with efficient minimum clique cover solutions
I would like to obtain a list of special graphs where there exist polynomial algorithms to find the minimum (vertex) clique cover. Some of the known cases are:
Perfect graph including bipartite ...
- 21
1
vote
1
answer
129
views
Bin Packing with mutual exclusive items. Goal: Minimum number of bins
I am asking for help for the following problem.
N items. Each Item has to be put into exactly one bin.
C constraints. Each constraints is a pair of items, meaning item x und item y are not allowed in ...
- 33
0
votes
0
answers
27
views
Is finding the number of solutions to a NP problem significantly harder than solving it?
I am wondering what is known about the problem of finding the number of solution to a NP-complete problem. We can of course take SAT as an example, it doesn't matter that much. It is clear that this ...
- 5,385