Questions tagged [np-complete]

Questions on the topic of NP-Completeness, which comes from Theoretical Computer Science

Filter by
Sorted by
Tagged with
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,...
NightShade's user avatar
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 ...
xMath's user avatar
  • 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 ...
Anwarul Azim's user avatar
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- ...
John Zimmerman's user avatar
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)$$ ...
braintorture's user avatar
-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 ...
larry's user avatar
  • 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\{ ...
Ariel Yael's user avatar
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?
ShyPerson's user avatar
  • 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 ...
SlimeyGuy123's user avatar
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 ...
Booker's user avatar
  • 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 ...
Booker's user avatar
  • 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 ...
MathCrackExchange's user avatar
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 ...
Mostafa Eid's user avatar
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 ...
Rodkaiser's user avatar
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 ...
anta's user avatar
  • 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 ...
John's user avatar
  • 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 ...
wormname's user avatar
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 ...
user122424's user avatar
  • 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 ...
qwerty43's user avatar
  • 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 ...
slithy_tove's user avatar
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-...
rogerhenry's user avatar
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 ...
Mathgineer94's user avatar
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 ...
Prboetic's user avatar
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 ...
Jeff's user avatar
  • 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 ...
Darcy Sutton's user avatar
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 ...
F.Hand's user avatar
  • 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\;\...
snatchysquid's user avatar
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 ...
Nate's user avatar
  • 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 ...
Francis's user avatar
  • 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 |$...
lia's user avatar
  • 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)...
RudeusGreyrat's user avatar
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 ...
FluidMechanics Potential Flows's user avatar
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 $...
edamondo's user avatar
  • 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 ...
Kai Arakawa's user avatar
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 ...
endeavor's user avatar
  • 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 ...
user1127725's user avatar
-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....
Efe çiğdem's user avatar
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 ...
Alex Breeze's user avatar
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 ...
mathoverflowUser's user avatar
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 ...
mghandi's user avatar
  • 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 ...
MariyaKav's user avatar
  • 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 ...
Jorge Martín Pérez's user avatar
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 ...
twixxerzz_13's user avatar
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 ...
diego.0412's user avatar
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 ...
Dave's user avatar
  • 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 ...
Ahmad's user avatar
  • 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 ...
diego.0412's user avatar
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 ...
firefighter's user avatar
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 ...
BenBar's user avatar
  • 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 ...
P. Quinton's user avatar
  • 5,385

1
2 3 4 5
14