Questions tagged [np-complete]
Questions on the topic of NP-Completeness, which comes from Theoretical Computer Science
472 questions
0
votes
1answer
17 views
A standard way to reduce a k-SAT to 0-1 Integer Linear Programming
I was searching for a standard (a published paper) for which it reduces a k-SAT to a 0-1 ILP (Integer Linear Programming), but couldn't find any :(
I know how to reduce a SAT problem to an ILP ...
4
votes
1answer
53 views
+50
What is a language “expressible” in second/first-order logic?
This paragraph in the wikipedia page of the P vs NP problem tries to explain a characterization of languages in P and those in NP, however this characterization is not very clearly stated.
Indeed, ...
0
votes
0answers
15 views
Reducing knapsack problem to a inversed knapsack problem
1)Suppose we have a common 0-1 knapsack problem. Given a set of n items numbered from 1 up to n, each with a weight w_i and a value v_i, along with a maximum weight capacity W. Here we need to select ...
0
votes
0answers
11 views
Domination problem is NPC
I call the problem as DOM. Given a graph $G$ and an integer $d$, Decision problem DOM - "Does there exists a dominating set of size less than or equal to 'd' in G? " DOM is NP Complete problem.
But, ...
0
votes
0answers
50 views
Reduce Hamiltonian Path Decision Problem To Hamiltonian Cycle Decision Problem
Person A requires that he determine whether or not a particular graph G = (V,E) has a Hamiltonian path from vertex a to vertex b.
His colleague Person B has implemented a function that takes an ...
1
vote
1answer
33 views
igraph - Minimum vertex set origin for destination
Part igraph question, part graph theory question. I have a digraph from a set of origin vertices (warehouses) to destination vertices (customers). A given origin vertex has edges only to a limited ...
3
votes
1answer
96 views
Is the following problem NP-complete?
Let $G=(V,E)$ be a directed graph and let $p_{ji}$ be the minimum path weight from $j$ to $i$; Then I can obviously save the path weights in a matrix $P$ similar to an edge weight matrix;
Now the ...
1
vote
0answers
38 views
Closest string attempted algorithm. [closed]
In theoretical computer science, the closest string is an NP-hard
computational problem, which tries to find the geometrical center
of a set of input strings.
To understand the word "center", ...
1
vote
1answer
69 views
Using the reduction of 3-SAT to 3-COLOR, explain why complexity proofs by reduction work.
I'm reading about the proof that 3-COLOR is in NP-Hard, by reduction of 3-SAT to 3-COLOR (as listed here for example: http://cs.bme.hu/thalg/3sat-to-3col.pdf). And here's a passage from Wikipedia, ...
0
votes
1answer
35 views
approximation algorithm for TSP and P=NP
i recently read an article about approximation algorithms for solving the TSP problem. One of the first theorems in this article states:
if there is an α-approximation algorithm for the TSP (...
1
vote
0answers
50 views
Is Elliptic Curve Discrete Logarithm Problem NP-Hard or NP-Complete
I have trouble classifying Elliptic Curve Discrete Logarithm Problem as NP-Hard or NP-Complete. Where does ECDLP belong? Any brief comprehensive answer is encouraged. Thanks.
0
votes
0answers
101 views
Proof of Validity of My Polynomial Time Algorithm for $co-NP$ Complete Problem
I posted an algorithm yesterday, that purported to solve the co-NP Complete 'Boolean Tautology Problem' in polynomial time.
Link to the algorithm : polynomial time algorithm
In that post, I presented ...
0
votes
1answer
33 views
Sudoku solution size
We know an $n$-Sudoku puzzle is with $n \times n$ subgrids consisting of $n \times n$ cells; you will fill it with numbers from $1$ to $n^2$.
Candidate solution have size polynomial in $n$, and can ...
1
vote
0answers
11 views
Faster boolean expression satisfaction
Few months ago I started to code message filtering for email. The filters are basically set of boolean operators, for example OR(Has(a), NOT(OR(Has(b),Has(c))), AND(Has(e), Has(f)))..., that decide ...
2
votes
1answer
27 views
how to find a solution of an np complete problem given a solution to another np complete problem?
Is it correct to say that give a solution (with any time complexity) to an NP-Complete problem it can be modified in some way so that it can solve all NP-Complete problems? If yes, then how can that ...
6
votes
0answers
60 views
Is this kind of “Gerrymandering” NP-complete?
Consider the following simplified form of "Gerrymandering": You have $n^2$ squares arranged as an $n\times n$ matrix. Each square is marked with either $0$ or $1$ which means a "voter preference" ...
2
votes
1answer
97 views
Reduction from 3-SAT to MAX 2SAT
For some time I've been trying to understand reduction of 3-SAT to MAX 2-SAT. I reviewed most of most popular books about computational complexity (Thomas Cormen, Papadimitriou) but I can't find an ...
0
votes
1answer
35 views
Is the generalized assignment problem with un-capacitated agents NP-hard?
I am working on a generalized assignment problem which I typed below. I know it is shown to be NP-hard. I am wondering whether the problem is still NP-hard when the capacity of the agents are assumed ...
1
vote
0answers
53 views
Filling a big rectangle with small rectangles
There are N numbers; their values are A1, A2, ..., An respectively, their sum is S. There is a big rectangle which area is S. You need to draw N number small rectangle which area is its value.
...
0
votes
0answers
13 views
How to solve $PARTITION$ using this optimization problem?
$PARTITON=\{<S>:\:S\:is\:a\:finite\:set\:of\:whole\:numbers\:and\:\exists T\subseteq S \:such \:that \sum T=\sum (S-T)\} \:$
The summation for $T$ for example is to sum all the numbers in $T$
...
1
vote
0answers
119 views
How can I prove that clust-p is NP-complete?
CLUST-P:
Instance: A a non-empty set, α : A × A → N, p, s ∈ N
Question: Does A have a partition, A1, A2, . . . , Ap, such that max α(u,v) <=s, u,v∈Ai ∀1 <= i <= p?
It is obvious that A ...
4
votes
2answers
81 views
Minimum transactions to settle debts among friends
You are given $n$ integers $x_1,x_2,\dots,x_n$ satisfying $\sum_{i=1}^n x_i=0$. A legal move is to choose an integer $a$ and two indices $i,j$, and to increase $x_i$ by $a$ and decrease $x_j$ by $a$. ...
0
votes
0answers
60 views
Number of divisors of a number - in NP?
I'm trying to show that the language $\{(m,n) | m \space \text{has exactly} \space n \space \text{divisors}\}$ is in NP.
The input $(m,n)$ is in binary.
The non-deterministic Turing machine for the ...
0
votes
1answer
24 views
satisfying boolean n variable DNF formula
I have an n variable boolean DNF formula and an input set,z consisting of n-tuples. Each tuple consists of truth/false assignment to n variable.
the number of tuples in Z is not fixed, obviously <= ...
1
vote
0answers
14 views
Reduction of Steiner Tree to Maximum Weight Connected Subgraph
I want to proof that the MWCS is an NP-hard problem by proofing that its decision version is NP-Complete. Below I have my proof so far and I hope people can give comments whether it can be formulated ...
0
votes
0answers
52 views
Set cover problem NP completeness
I have a quick question about Set cover problem. In Wikipedia, < https://en.wikipedia.org/wiki/Set_cover_problem >, they are saying "The decision version of set covering is NP-complete, and the ...
0
votes
1answer
53 views
Show that the 3-color problem is in P when the input graph is a tree.
This one is from university assignment. I am completely stuck on this one and I searched the internet but couldn't find a explanation.
Show that the 3-color problem is in P when the input graph is ...
0
votes
0answers
22 views
Partition Problem Variant
I'd like to ask to solve a variant of set partition problem. Suppose we have some items $V = \{1, \cdots, n\}$ and a subadditive cost function $f: 2^V \to R^{+}$. For any partition $P$ of $V$, define ...
0
votes
0answers
11 views
Complexity of maximizing sum of fractional functions under cardinality constraint
Considering the following optimization problem:
$max_{x} \ \sum_{i=1}^n \frac{W_i}{D_i - z_i},\quad s.t.\ \sum_{i=1}^n z_i \leq k,z_i\in[0,k]$, where $W_i$ and $D_i$ are postive constants and $z_i$ ...
1
vote
1answer
68 views
Maximizing the total number of feasible constraints of a linear program
I have an optimization problem with $N$ linear inequality constraints and $K$ real valued parameters (e.g. $0.2\alpha_1+0.5\alpha_2\geq 0$, $K=2$) and no objective function. Here $N$ is much larger ...
0
votes
1answer
38 views
Positioning items to maximize separation subject to constraints
Say we want to place n items on the real line. Let us denote the position of item i by $p_i$. We have interval constraints on the position $p_i$, i.e. we are given $l_i, r_i$ such that $l_i \le p_i \...
1
vote
0answers
82 views
Is the Maximum Clique Problem for Directed Acyclic Graphs NP complete as well?
Imagine I have a graph $(V,E)$ of vertices $V$ and undirected edges $E$. Then a clique is a set of vertices $(v_1,...,v_n)$ such that that there is an edge between any pair $(v_i,v_j)$ of vertices ...
5
votes
3answers
114 views
Why can't set cover be reduced to min-cost max-flow?
Okay, so I know obviously I'm making some kind of easy mistake here, since set cover is NP-complete and min-cost max-flow is in P, but I can't figure out what the mistake is.
So, given a universe $U$ ...
0
votes
0answers
12 views
Karp hardness of a module in a graph
DEFINITION: A set of vertices $A\subseteq V$ in a graph $G(V,E)$ is called a module if it satisfies the following property:
For every $v\in V\setminus A$, either $A\subseteq N(v)$ or $A\cap N(v)=\...
1
vote
0answers
25 views
NP-hardness proof of a model with a convex objective
Let $T=(V,E)$ denote a tree. Each node $j \in V$ in the tree has a known attribute $c_j$.
From T, construct a bi-directional graph $G' = (V, E')$ where $E' = \{(j,k), (k,j)| (j,k) \in E\}$. Simply, ...
0
votes
0answers
68 views
A Language in CNF with distinct variables per clause and each variable appears in at most three literals is in P
Let A be a language defined thus
A = {φ | φ is in CNF, with three literals, comprising distinct variables, per clause;
and each variable appears in at most three literals; and φ is satisfiable} .
...
0
votes
1answer
34 views
NP Completeness of a Graph Problem, Proof Required
I have a graph problem that I would like to prove NP-completeness. It is outlined below:
A graph problem compromising of two graphs, say $G_1(V_1,E_1)$ and $G_2(V_2,E_2)$ such that $V_i$ and $E_i$ ...
0
votes
1answer
37 views
Why is showing that ILP in NP not trivial
I have a question regarding the topic of showing that ILP is in NP
What is the problem with Guess and Check?
Guess a solution and then check if it is optimal.
Or further:
Calculate a solution via ...
1
vote
1answer
37 views
Is the n-Queens problem only np-complete for the task of finding all setups or also for finding any solution?
I have read on Wikipedia that the n-Queens problem is NP-complete when it comes to finding all possible solution implies it that finding one possible solution is also NP-complete?
0
votes
1answer
25 views
Big-O for $\Sigma_{i = 1}^{N} i \times \binom{N}{i}$ [closed]
How to solve Big-O for $\Sigma_{i = 1}^{N} i \times \binom{N}{i}$? Can I simply say it is in $O(N!)$?
2
votes
1answer
33 views
GI-Completeness of graph isomorphism with connected graphs
The Wikipedia page for Graph Isomorphism lists connected graphs as GI-complete. The citation has a paywall, and I have not been able to find any NP-complete algorithms for isomorphism of connected ...
1
vote
0answers
82 views
How to prove a submodular maximization problem is NP-hard
We know that a submodular maximization problem of the form
$$
\mathcal{P}: \,\, \mathop {\max }\limits_S f\left( S \right)
$$
where $f(S)$ is a submodular set function, is NP-hard (Claim 1).
This ...
3
votes
1answer
152 views
Properly stating a decision problem for a Hamiltonian cycle problem
I'm running an algorithms seminar and I'm trying to express the Hamiltonian cycle problem in a new way that is exciting to students. I know that many of them play a game called Hearthstone and I'm ...
0
votes
0answers
38 views
Proof for correctness of reduction from 3-SAT to quadradic equations NPC problem
A reduction from 3-SAT to quadratic equations is described as follows:
Given an input expression to 3-SAT, convert it to a quadratic example as follows:
$x_i \rightarrow ax_i$
~$x_i \rightarrow a(1-...
1
vote
1answer
119 views
Does this solve boolean satisfiability problem in polynomial time?
CNF can be easily converted into a formula that uses only AND and NOT operations, using the fact that ...
3
votes
0answers
44 views
Looking for name of combinatorial problem- Permute rows and columns to minimize distance to target matrix
I am trying to find a solution (or algorithm) for the following combinatorial problem:
Given an input matrix and a target matrix, find a permutation of the rows and permutation of the columns that ...
0
votes
0answers
202 views
how to convert SAT to 3SAt
My teacher showed these steps when converting SAT to 3SAT (he was working with an example).
He said to construct a formula F1
...
0
votes
0answers
27 views
NP-hardness of finding the zero norm of a sparest null vector
The abstract of the paper The Null Space Problem I. Complexity states that finding a sparsest null vector of a matrix with more columns than rows is NP-hard (actually NP-complete). I wonder whether ...
0
votes
1answer
59 views
If a NP-complete problem is not in P, then all NP-complete problems are not in P?
It is clear to me that if a NP-Hard problem is solvable in P, then all NP-Hard problem (which include NP-Complete problems) are solvable in P.
But, is it also the case that if a NP-Complete problem ...
0
votes
0answers
21 views
USAT, Arora Barak's book
Here on the page 354 Arora and Barak write below the shaded area
"but in fact $f(\phi)$ $\notin SAT$"
and not
"but in fact $f(\phi) \in SAT$"
While in the last line of the shaded area they write
$...
