Questions tagged [np-complete]
Questions on the topic of NP-Completeness, which comes from Theoretical Computer Science
572
questions
0
votes
0answers
11 views
APX-hardness - Sufficient condition
I am currently analyzing the complexity of the following problem:
Input: Matrices $M_1 \in \mathbb{R}^{n\times m_1}$, $M_2 \in \mathbb{R}^{n\times m_2}$, and vector $c \in \mathbb{R}^{n}$.
Question: ...
2
votes
1answer
11 views
Min Max diameter of subgraphs from a given graph.also given the number of subgraphs.
Given a graph and the number of groups we want to divide the graph into, Find the best way to divide the graph, such the max diameter of all the groups is minimum
The graph is undirected, the number ...
1
vote
1answer
15 views
The concept of the creation of a trapdoor in NP-complete or NP-hard problems
I am reading the book An Introduction to Mathematical Cryptography. In its chapter 7, there is the following statement:
In real world scenarios, cryptosystems based on NP-hard or NP-complete problems ...
2
votes
1answer
91 views
How do you turn a proof of a mathematical statement into a zero-knowledge proof?
I recently watched a video on Numberphile2 in which Avi Wigderson describes how one can prove a graph has a 3-colouring in zero-knowledge and that as 3-colouring is NP-complete, all NP statements have ...
-1
votes
1answer
20 views
Fact Check: Is any maximum clique also a maximal one?
According to Wikipedia:
A maximal clique is a clique that is not included in a larger clique.
and
A maximum clique is a clique that includes the largest possible number of vertices.
0
votes
1answer
25 views
Dominant subset in bipartite graph NP-complete proof
Let the dominant subset problem (which is known to be NP-complete) be:
Given a graph $G=(V_G,E_G)$ and an integer $k$, is there a subset $W \subset V_G$ with at most $k$ vertex so that any other ...
0
votes
0answers
19 views
How do i solve these 2 NP complete problems?
A1, A2, A3 ⊂ A in pairs of 2 they have NO common spot. Their union is A and they have same sum.
How can i see this is NP complete .
Second Problem.
A = {a1, . . . , an}
How do i see if a, b, c, d ∈ A ...
1
vote
1answer
33 views
Proof that “partition problem in proportion 2:1” is NP-complete
I need to show that problem "partition problem 2:1" is NP-complete.
I know that I need to use $A'$ as certificate to proof that problem is NP.
I know that "partition problem":
...
0
votes
0answers
13 views
which similar np hard problem can be used to reduce timetabling problem?
I have a set of courses and each courses have a set of classes. Each classes have a set of timings available with some penalty. I wanted to schedule each classes to any of the timings of its with a ...
0
votes
1answer
49 views
Is Time scheduling problem np hard or np complete?
I have a set of courses and each courses have a set of classes. Each classes have a set of timings available with some penalty. I wanted to schedule each classes to any of the timings of its with a ...
0
votes
0answers
26 views
NP-Complete polynomial/linear transformations
I have been revising standard reductions for the following NP-complete problems:
SAT to 3SAT
3SAT to VERTEX COVER
VERTEX COVER to INDEPENDENT SET
INDEPENDENT to SET CLIQUE.
I understand that since ...
0
votes
0answers
20 views
Solving a multivariate linear Diophantine system with constraints
I'd like to know if there is an efficient way to solve the following class of systems of linear Diophantine equations because I think some variants of the problem are NP-hard whereas others are not:
...
3
votes
3answers
109 views
Using Bellman-Ford to find a Hamiltonian cycle? (NP-complete)
Let $G(V,E)$ be a directed graph, where $V=\{a_1,\ldots,a_n\}$ is a set of vertices and $E$ is a set of ordered pairs of $V$, with $|V|=n$.
Now, let be $G(W,F)$ be a graph where $W$ is a set of ...
-1
votes
1answer
65 views
Graph minus a point has a separation
(It's wrong there is a separation even for for a graph with a basic Hamiltonian path.)
Let G(V,E) be a connected (no separation) directed graph, such that, $S_x$=V∖{x}, ∀x∈V is a subset of vertices of ...
0
votes
1answer
40 views
Is there any such NO-answer example for Betweenness (TOP) problem?
Problem Statement
The input to a betweenness problem is a collection of ordered triples of items. The items listed in these triples should be placed into a total order, with the property that for each ...
6
votes
1answer
206 views
Is XOR-SAT + $2$-SAT in P?
I read in a paper a proof where you can reduce a $3$-SAT problem into $2$-SAT + HORN-SAT clauses.
$2$-SAT + HORN-SAT is therefore, NP-complete.
$2$-SAT, HORN-SAT, DUAL HORN-SAT, XOR-SAT are all in P.
...
0
votes
1answer
42 views
Graph minus a point has at most 2 connected components
Let $G(V,E)$ be a connected undirected graph (undirected=easier), such that, $S_x=V\setminus\{x\}, \forall x \in V$ is a subset of vertices of G. Then the induced subgraph $G[S_x]$ is the graph whose ...
3
votes
1answer
116 views
Is this problem NP-hard?
Is the following problem NP-hard?
Let $Ax=b$, where $a_{i,j} \in \{0,1\}, b_i \in \{0,1\}, x_j \in \{0,1\}$.
Decide, wether there is a solution or not.
2
votes
1answer
122 views
Can travelling salesman be translated into a SAT problem? [closed]
I read that all NP-complete problems can be translated into one another.
I can't see how the travelling salesman problem which involves distances which are real numbers can be translated into a ...
0
votes
0answers
18 views
P-NP Approximation algorithm
Define an independent set of a graph $G = (V, E)$ to be a subset $S$ of vertices such that $V-S$ is a vertex cover of $G$. Is every 2-approximation algorithm for finding a minimum vertex cover also a ...
1
vote
1answer
33 views
NP-completeness of undirected planar graph problem
I want to know whether a certain graph problem is NP-complete or not. The problem is as follows.
Given an undirected planar graph with in every vertex a number. Can you give every edge a direction ...
0
votes
0answers
19 views
NP-completeness of bipartite planar graph problem
I want to know whether a certain graph problem is NP-complete or not. The problem is as follows.
Given an undirected planar bipartite graph with in every vertex a number. Can you make a subgraph for ...
0
votes
2answers
21 views
Construct a TM to show that {<G,s,t,k> | G is a directed graph with path length $\le$ k from s to t} is in class P
I would like to construct a deterministic TM that decides $L=${$<G,s,t,k>$ | $G$ is a directed graph that has a path of length at most $k$ from vertex $s$ to vertex $t$} in polynomial time.
So ...
0
votes
1answer
34 views
P-NP for decision problems
The final quiz problem asked whether the statement
For decision problems L1, L2 in NP, if P is not NP, L1 is at least as hard as L2, and L2 is at least as hard as L1, then L1 and L2 are NP-complete
is ...
0
votes
1answer
24 views
P-NP related problems
This is a question on a practice final.
Which of the following statements are true? If it is false, what is the underlying reason behind that?
I. If 3-CNF-SAT is in P, then Clique is also in P.
II. ...
1
vote
0answers
49 views
Two problems related to NP-Hard and why they are true?
$F(z_1,...,z_n)$ is a Boolean expression. The assignment of variable ($x_1,...,x_n \in {0, 1}$) is the answer of $F$, if $F$ for that assignment equals to $1$.
If that case is true and the conditions ...
1
vote
0answers
16 views
Proving $\{(C,x): C(x) = 1 \ \ \text{and} \ \ C \ \ \text{is monotone}\}$ is P-complete
I'm currently studying about circuit complexity, stumbled upon this language, trying to prove it is P-complete:
$$\{(C,x): C(x) = 1 \ \ \text{and} \ \ C \ \ \text{is monotone}\}$$
a circuit is ...
4
votes
1answer
153 views
NP, NP-complete and Reducibility
Suppose there is polynomial time reduce from problem $A$ to $B$.
fact $1)$ if problem $B$ is $NP$-hard then Problem $A$ is $NP$-complete.
fact $2)$ if problem $A$ is $NP$-complete then Problem $B$ is $...
0
votes
1answer
35 views
np hard and np complete simple question
I need a very short and simple description for my doubts about some concept in following:
all NP-Complete problems can be reducible to all problems in NP-Hard.
any np-hard problem can be reducible to ...
0
votes
0answers
22 views
NP closed under Kleen Star (Proof step misunderstood)
I had a question about the proof that NP is closed under *.
Here is the proof I'm using, from Sipser's
We make a non deterministic Turing machine that decide L * in non deterministic polynomial time.
...
1
vote
0answers
17 views
Could there be a sequence of polynomial time algorithms for NP problems?
Assuming there is no polynomial algorithm for a general NP problem. There might be an alternative.
For example. Consider the Travelling salesman problem on N nodes.
There may be a sequence of ...
0
votes
1answer
34 views
What commands would a P=NP algorithm consist of?
Taking the example of boolean satisfiability problem. We might have something like:
$$(a \lor b \lor c \lor d)\land (a \lor d \lor e) \land (f \lor b \lor g)$$
The statement is that there is no ...
0
votes
1answer
53 views
Knapsack, but divided by summation
For a given set $S = \{1, 2, ... , N \}$, each component $i\in S$ can be represented by $(a_i, b_i, c_i, w_i)$. Is there any technique for solving the following problem?
$$\max_{S' \subseteq S} \frac{ ...
0
votes
1answer
27 views
NP hard (like KNAPSACK)- any approximation scheme?
For a given set $S = \{1, 2, ... , N \}$, each component $i\in S$ can be represented by a triple $(a_i, b_i, c_i)$. How can the following be solved? Any polynomial time algorithm exists?
$$\max_{S' \...
1
vote
1answer
40 views
Converting a 4cnf clause into one with not all equal literals
Given a 3cnf clause $$(a \lor b \lor c)$$ we can construct an equivalent conjunction $$(a\lor b\lor d) \land (\lnot d \lor c \lor \bot)$$ such that the second clause has a valid truth assignment if ...
3
votes
1answer
98 views
(soft question) Why are there so many NP-complete problems?
The definition of NP completeness feels very restrictive. For a language $L$ to be NP complete, everything in NP must reduce to it in polynomial time and yet it must still be in NP itself.
There is a ...
3
votes
0answers
51 views
Subset sum problem for geometric sequences
Problem Statement
Update: This problem has an update. See Edits section at the end.
Given a finite set $A \subset Z$, the Subset Sum Problem is a decision problem that answers the question Does any ...
2
votes
1answer
44 views
Finding exactly n vectors that xor (sum in GF(2)) to x
Given a set of vectors S, finding a subset s that XORs to x is trivial: Use Gaussian elimination under GF(2). Moreover, any such subset can be found by adding arbitrary members of the matrix's ...
0
votes
0answers
21 views
How to prove this p-median-like problem is NP-hard?
I am try to figure out whether the following problem is NP-hard? The setting is as follows: we have $N$ servers and certain amount $F$ of resource. We need to select $M$ servers ($M \le N$) and ...
1
vote
1answer
49 views
$P$ vs $NP$ characterization confusion
I know that $P \subseteq NP$, but for a problem in $P$, e.g. MST in a graph, is it a correct statement to say that:
The MST problem belongs in $NP-\text{Class}$.
(I mean, i think it is correct, but ...
1
vote
2answers
37 views
'Finite' Approximation of Languages
Is it true, that for any finite language, there is a Turing Machine that runs in polynomial time that accepts said language?
It seems to me that this would imply that given any number $N$, any ...
1
vote
0answers
41 views
Set Cover Optimization of Cubes by Balls of Equal Radius
Let $C=[a,b]\subset R^n$ be a $n$-dimensional rectangle, $a,b\in R^n$. Find the minimal radius $r$ and set $x_1, \dotsc, x_N\in R^n$, for a given integer $N$ such that
$$\bigcup_{i=1}^N B_r(x_i) \...
0
votes
1answer
120 views
Karp reduction from HC to HP. What am I doing wrong?
I know there is this solution for Karp reduction from HC to HP in here (INDIRECTED graph).
But I was thinking about something else, and would like to know what you think about it.
I create 2 new ...
0
votes
0answers
41 views
How can I prove the language 3COL is reducible to the language SAT?
3COL : Language describing all the possible ways of coloring a graph with three colors.
SAT : Language describing all satisfiable boolean formulas.
My goal is to demonstrate that 3COL $\leq_{p}$ SAT. ...
1
vote
1answer
35 views
How to prove that there is closure in NP for the reverse operation on strings?
I have a language A which is known to be in NP. I want to know that if I have the language $A^R$ which takes in $w^R$ which is a word of A but read in reverse will it still be in NP?
I tried to prove ...
1
vote
0answers
23 views
Is knapSack 0-1 problem where weights equal to costs is also NP hard?
From wiki:
Given a set of items, each with a weight and a value, determine the
number of each item to include in a collection so that the total
weight is less than or equal to a given limit and the ...
1
vote
1answer
45 views
Equivalence of NP-complete problems
I am currently studying the concept of NP - complete, and I came across a question that I'm not sure about my own answer (currently, it's a "Yes."). The question is: assuming Problem A ...
0
votes
0answers
38 views
Nondeterministic polynomial time algorithm versus certificate/verifier for showing membership in NP
Edit: An answer is available here: https://cs.stackexchange.com/questions/128388/nondeterministic-polynomial-time-algorithm-versus-certificate-verifier-for-showi/128391?noredirect=1#...
3
votes
0answers
75 views
Number of subsets $S \subset A_1 \cup A_2 \cup … A_n$ where $|S \cap A_i| = a_i$?
Given potentially non-disjoint sets $A_1, A_2, ... A_n$, how many subsets $S \subset \bigcup A_i$ exist where
$$|S \cap A_i| = a_i$$
for $0 < i \leq n$.
For $n = 1$, the answer is $\binom{A_1}{a_1}...
0
votes
1answer
28 views
Convexity and NP-hardness
Suppose that we have the following optimization problem:
$$Maximize_{x_{j,i}} ~ {{\sum_t \sum_i \sum_j (a_{0,i;t}+\sum_i \sum_j a_{j,i;t} x_{j,i;t})}\over{\sum_t\sum_i\sum_j x_{j,j;t} b_{j,i;t}}}$$
$$...
