Questions tagged [np-complete]

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

Filter by
Sorted by
Tagged with
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}}}$$ $$...

1
2 3 4 5
12