Questions tagged [np-complete]

Questions about the hardest problems in NP, i.e. of those that can be solved in polynomial time by nondeterministic Turing machines.

Filter by
Sorted by
Tagged with
0
votes
1answer
12 views

Reduction from Clique to IS degree at most 4

This is from the Algorithms textbook by Dasgupta,C. H.Papadimitriou,andU. V. Vazirani question 8.6 (b) that asks: My reduction from Clique: Definition of clique: fully connected graph/subgraph So ...
1
vote
1answer
31 views

How to prove NP-completeness of this mail-problem?

Let's say we have n postmen that are bringing people mail in a neighbourhood, and that they start and end at the same post office. This situation can be decribed with a directed graph, where the ...
3
votes
1answer
22 views

Minimal Path Covering

Consider a connected undirected graph $G = \langle V, E\rangle$, we say that a subset $C$ of vertices is a Path-Cover if the following holds. For every finite path $p$, it holds that $p$ traverses all ...
2
votes
1answer
63 views

How does strong NP-completeness agree with encoding complexity?

I've recently read about the concepts of weak and strong NP-completeness, but faced a problem in wrapping my head around them. I've understood that problems which have numerical parameters (like ...
0
votes
0answers
31 views

prove that Integer partition problem is NP complete using Hamiltonian Cycle

Show that Integer parition problem is NP-complete using the fact that Hamiltonian cycle is NP-Complete My Thoughts : Integer paritition problem is about partitioning a given set of integers into two ...
2
votes
1answer
98 views

What are the exponential alternatives that are skipped in dynamic programming for longest increasing subsequence?

I am trying to wrap my head around how dynamic programming helps avoid all possibilities that are exponential after reading Chapter 8 NP-complete problems of Algorithms by Dasgupta et al. where it ...
0
votes
1answer
32 views

Relevance of depth for $NP$-completeness of fan-in $2$ and fan-out $1$ modest depth circuits?

Let $\mathcal C$ be a circuit of $m=f(n)$ input wires where every input is taken in the set $\{x_1,x_1',\dots,x_n,x_n'\}$ where $x_n\in\{0,1\}$ and $x_n+x_n'=1$ holds (not all $x_i,x_i'$ necessarily ...
1
vote
1answer
105 views

Reductions versus generalizations

I am reading Chapter 8 NP-complete problems in Algorithms by Dasgupta et al and looking at some questions at the end of the chapter. My own questions are below (after the image with the textbook ...
1
vote
0answers
10 views

How are randomized restarts in local search 4 times likely to give bad local minima?

I am reading section 9.3.3 Dealing with local optima in Algorithms by Dasgupta et al. and the authors mention that in randomized restarts, it is four times likely to end up with a bad solution. They, ...
1
vote
1answer
25 views

Greedy approach suggestions for assigning objects

Suppose there are three categories of people. Type X, Type Y, Type Z. In each type, there are two objects of subtype Type 'a' and type 'b'. For example. X: a1 , a2 , b1 , b2 Y: a3 , a4 , b3 , b4 Z: a5 ...
-2
votes
2answers
80 views

Does NP-hard problems have to be decision problems? (What the fact please) (contradicting answers)

Let me explain my trouble by another example. The wiki page says that Lattice problems are an example of NP-hard problems However, by clicking NP-hard, i find this definition A decision problem H ...
0
votes
1answer
41 views

Is O(1) considered polynomial time?

I am reading about P and NP and looking at the reduction of a Rudrata/Hamiltonian path to a Rudrata cycle. I think adding an extra node and 2 edges connecting the start, ...
-1
votes
1answer
28 views

Reduction from $VC$ to $CD$

We define the vertex cover as the problem of finding for a graph $G$, a cover of size $k$. A cover is a set of vertices such that every vertex has an edge to this set. We define CD (cycles destructor),...
-1
votes
0answers
36 views

NP-completeness of disjoint paths with bounded common nodes [duplicate]

Given an undirected graph $G=(V,E)$, $k$ distinct node pairs $(s_1, t_1), ..., (s_k, t_k)$ and an integer $\delta$, determine if there exist $k$ edge-disjoint paths from $s_i$ to $t_i$ $(1\leq i\leq k)...
2
votes
0answers
44 views

3-cycle cover decision problem for directed graphs: best known algorithm and maximum size of tractable problems

I know that the 3-cycle cover decision problem for directed graphs (3-DCC), defined as finding whether a directed graph has a disjoint vertex cycle cover in which every cycle has at least 3 edges, is ...
0
votes
0answers
33 views

IF satisfiability problem belonged to P, can the certificate be found efficiently?

IF SAT(satisfiability problem) belongs to P, then is it possible for a certificate of an arbitrary instance of SAT to be found efficiently?
1
vote
0answers
42 views

Strong NP-completeness of numerical perfect matching

This is a follow-up to post Perfect matching problem, where nir proved weak NP-completeness. Suppose you are given two sets of integers $L$ and $M$ both having $N$ elements. We want to match each ...
1
vote
1answer
27 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 ...
1
vote
1answer
30 views

Reduction for the proof that COMBI $:= \{\langle G,k \rangle | G$ has Clique $\geq k$ or Independent Set $\geq k\}$ is NP complete

Given the Language $COMBI := \{\langle G,k \rangle | G$ has Clique $\geq k$ or Independent Set $\geq k\}$. Proof that Combi is NP-complete. I tried to reduce Clique <=p Combi. I had two different ...
0
votes
0answers
31 views

Is there any proof that says “For each problem in NP there is a randomized algorithm that solves that problem in expected polynomial time.”

Is it known that "For each problem in NP there is a randomized algorithm that solves it in polynomial time"? If not true then is there any proof of that. Or does it belongs to the unknown ...
0
votes
1answer
59 views

Minimum absolute value of subset sums of integer values

$f(x_1,...,x_m)=\min_{\emptyset\subset I\subseteq[m] }\left|\sum_{i\in I}x_i\right|, x_i\in \mathbb{Z}\setminus\{0\}$ How to prove $f\in \mathbf{POLY} \Leftrightarrow \mathbf{P}=\mathbf{NP}$? When $\...
1
vote
1answer
28 views

$\overline{SAT}$ vs. $UNSAT$, Is it the same?

I know this question may look stupid, but still.. Is the meaning of both "have no satisfiable assignment"?
-1
votes
1answer
42 views

Is this exponential-sized vertex cover problem in P?

Suppose P $\neq$ NP. Prove or disprove if language is in P using a reduction or an algorithm: $$ \left\{ \left(G = (V,E), k, 0^{2^{|V|}} \right) \mid (G,k) \in VC \right\} $$ Suppose I have the this ...
25
votes
4answers
5k views

Why is SAT so important in theoretical computer science?

In my Computability and Complexity class, we are focusing on P, NP, NP-complete, and NP-hard problems and the one thing that keeps coming up is the SAT problem, in the context of reduction from one ...
-4
votes
1answer
31 views

Finding a clique in undirected graph is P or NP? (proof) [duplicate]

Finding a clique $C$ in an undirected graph $G= (V, E)$ such that $|C| > |V|/2$ is in P or NP-hard? How can I prove it?
1
vote
1answer
43 views

How to check if an algorithm's running time is linear/polynomial in its input size? Multiple variables

I am reading a proof that the Subset Sum decision problem is NP-complete. I know that the time complexity is always calculated based on the number of bits of the input in binary, hence the $\log{W}$. ...
0
votes
1answer
27 views

Reducing the Hamiltonian cycle to the travelling salesman problem and self loops

If this is my adjacency matrix for the hamiltonian cycle: $$\begin{pmatrix}0&1&0&1\\ 1&0&1&0\\ 0&1&0&1\\ 1&0&1&0\end{pmatrix}$$ Then a reduction ...
14
votes
1answer
3k views

Hardness of a problem which is the sum of two NP-Hard problems

Consider the problem of computing an exponential sum over a certain function $g(x)=f(x)+h(x)$, that is computing $$\sum_{x}g(x)=\sum_{x}f(x)+\sum_{x}h(x)$$ now if we know that $\sum_{x}f(x)$ and $\...
2
votes
0answers
58 views

P/NP - Proof that SAT-TM is NP-complete uses certificate

To prove that SAT-TM (Turing machine emulating the satisfiability problem) is NP-Hard $$\text{SAT-TM}:=\{⟨M,p,1^k⟩ \; | \;∃c,\; |c|\leq p(k), \;\text{such that M accepts c in ≤k steps}\}$$ my ...
0
votes
2answers
71 views

Have I proven P equals NP if I find an amortized O(n) algorithm for Subset Sum

I have found an algorithm that runs quite fast on Subset Sum problem few years ago (sometime around 2016). It basically sorts the input set in descending order (instead of the regular ascending) and ...
1
vote
4answers
114 views

If $A$ reduces to $B$ and $B$ is NP-hard, is $A$ NP-hard?

Suppose there is a polynomial time reduction from problem $A$ to $B$. Why is the following false? If $B$ is NP-hard then $A$ is NP-hard. Can some explain this intuitively?
0
votes
2answers
107 views

Is Bitcoin mining NP-Hard?

I can't find this anywhere online. Is bitcoin mining NP-Hard? If so, how would we be able to prove a reduction from a known NP-hard problem? I am a bit lost.
2
votes
1answer
38 views

Clarifying the definition of reduction with regards to NP-complete problems

In my logic class we started learning about the different complexity classes. In particular, we focused on the NP complexity class. A problem is in NP if it is solvable in polynomial time using a ...
2
votes
2answers
83 views

Maximize number of subsets

Given a list of subsets $S_1, \ldots, S_n$ of the universal set $U = \{e_1,\ldots, e_m\}$, find a subset $S \subset U$ of size $k$ that contains the maximum number of subsets $S_i$. In another words, $...
2
votes
1answer
48 views

$k$-SAT completeness proof when $k$ is linear in number of variables

I'm looking at a special version of SAT in which each clause has exactly $n/2$ literals, where $n$ is the number of variables. Can we prove NP-completeness of SAT in this case? I tried reducing 3-SAT ...
1
vote
1answer
22 views

Is this “superset existence” problem NP-complete?

The "Superset Existence Problem": Let there be a set $S$, and $x$ subsets of $S$. Does there exist a set of size $y < |S|$, which is a superset of at least $z$ of those subsets? To me, ...
2
votes
2answers
76 views

Find maximal clique consisting of at least half of the vertices

Assume that we are given an undirected graph $G$ of n vertices. For this graph, we also know that there is a clique of size $c$, for some $c\geq \lfloor n/2 + 1\rfloor$. In other words, the majority ...
1
vote
1answer
110 views

NPC-problem reduction to triangle-free 3-colorability

lately, I have encountered a problem that I struggle to find a satisfactory solution for. I need to prove that triangle-free 3-colorability is NP-complete. Therefore I assume the right way is to find ...
0
votes
1answer
48 views

Reduce Clique to N-Degree-Clique

I want to show that there is a polynomial-time reduction from the standard $\text{Clique}$ problem to the $\text{N-Degree-Clique}$ problem, where: $$ \text{N-Degree-Clique} = \{ \langle G, k\rangle: \...
1
vote
1answer
63 views

Understanding P vs NP

I want to make sure my understanding on P vs NP is correct. I know that NP-complete problems cannot be solved in polynomial time, and if P != NP, then all problems in NP cannot be solved in polynomial ...
2
votes
1answer
43 views

Graph partition that maximize the number of triangles within its parts

Given a graph $G = (V,E)$, how to partition $V$ into $k$ parts $P_1, P_2, \ldots P_k$ of at most $M$ vertices, such that the number of triangles (3-cliques) contained in the parts is maximal? This ...
1
vote
1answer
33 views

Cyclic tour minimizing total weight

I asked the following question on math.se but it wasn't really answered so moved it over here as I feel it's more relevant. I saw the question below on an old stack exchange question when looking to ...
0
votes
0answers
30 views

Difference longest path problem and underlying decision problem [duplicate]

I am studying the longest path problem with the final objective to show that it is NP-complete. On wikipedia I read that the problem itself is NP-hard but the underlying decision problem is NP-...
2
votes
1answer
54 views

Difficulties proving when a language is in P or is NP-complete

I have some difficulties in understanding how to prove when a language is in P or is NP-Complete. Specifically, consider the following decision problems w.r.t undirected graphs $G = (V, E)$: $L_1 = \{...
-2
votes
1answer
75 views

How does one sketch a proof to show that the following problem is in the P Complexity Class?

I have the following problem. I do not know where to start or how I should approach this problem. I am not sure about how to prove if a problem is in a complexity class of P . I know how to do NP but ...
0
votes
0answers
20 views

How many strings for CLOSEST STRING lower bound to apply

In the CLOSEST STRING problem, one is given (bit-)strings $s_1, \dots, s_t$, each of length $L$ and an integer $d$. The question to be answered is whether there exists a string $s$ that has hamming ...
0
votes
1answer
79 views

4 Vertex Cover Problem is not NP Complete why?

With Given Graph $G$ why finding that $G$ has a vertex cover of at most $4$ is in $P$ and Not in NP Complete. it means there us poly-time algorithm for this problem !!?
0
votes
1answer
30 views

maximum Hamilton cycle and NP-completeness

we know max tsp (maximal Hamilton cycle) is NP-Hard. is there any decision version for this problem to conclude this is NP-Complete?
0
votes
1answer
101 views

How to prove that the subset sum problem is polynomially reducible to the knapsack problem

I want to prove that the subset sum problem is polynomially reducible to the Knapsack problem. Overall I want to show that Knapsack is NP-complete. There are two parts to showing knapsack is NP-...
0
votes
0answers
53 views

Is the Maximum Independent Set problem NP-complete? [duplicate]

It can be read on Wikipedia that MIS is NP-hard. However, is it also NP-complete? This article says: "Thus, the Maximum Clique Problem(MCP) and the Maximum Independent Set(MIS) Problem are ...

1
2 3 4 5
26