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
40 views

Karp's reduction strategy

One way to prove that a problem $X$ is NP-Complete is to pick two NP-Complete problems $Z$ and $W$ and show that ($\leq_p$ is polynomial reduction): $$\begin{array}{rr}X \leq_p Z & (1)\\W \leq_p X&...
1
vote
2answers
31 views

Are joins/pullbacks of bloom filters possible?

An interesting advantage of bloom filters over hash tables, that they share with bitarrays, is that they support taking unions & intersections of sets by simply doing bitwise or & bitwise and ...
0
votes
0answers
34 views

How can I randomly sample from the set of NP Complete problems?

I'd like to create some program that can keep spitting out verification algorithms. My verification algorithms take two inputs: problem instance, and solution (both encoded in binary), and output True ...
1
vote
1answer
49 views

How to show that this problem is NP-hard: Find two subsets of 2 given sets such that the difference between the subset sums is $\leq v$

As input, given two finite sets of integers $X = \{x_1,...,x_m\}$, $Y = \{y_1,...,y_n\} \subseteq Z$, and a non-negative integer $v ≥ 0$. The goal is to decide if there are non-empty subsets $S ⊆ [m]$ ...
1
vote
1answer
85 views

There is an $n^k$ prover if and only if $P = NP$

I am studying computational complexity using Papadimitrious's book: "Computational Complexity". I am trying to solve the final statement of Problem 8.4.9, but I am stuck and would like some ...
7
votes
0answers
47 views

P=NP turns 50. 1971 STOC conference

Stephen Cook presented his seminal paper "The complexity of theorem-proving procedures" at the 1971 STOC (Symposium on Theory of Computing) conference which was held May 3-5, 1971 at Case ...
1
vote
2answers
70 views

Proving a problem is NP Hard

Consider the following problem: Given a weighted directed graph $G$, determine if $G$ has a cycle whose total weight is $k$. All edge weights are integer but might be negative. $k$ is not an inputted ...
1
vote
1answer
48 views

Reduction from SUBSET-SUM to 0-1-INT-PROG

The 0-1-INT-PROG problem is given an integer $m \times n$ matrix $A$ and an integer $m$-vector $b$, is there an integer $n$-vector $x$ with $A \cdot x \leq b$. I am trying to prove that 0-1-INT-PROG ...
17
votes
4answers
4k views

Is the following problem NP-hard? (or have you seen it before?)

I genuinely don't know if the following problem is NP-hard. I have never seen it mentioned online, but it's hard to even search for exact problems like this. I have been trying to find an efficient ...
1
vote
1answer
112 views

How can I prove the following problem is NP complete?

The problem: I have a list $\displaystyle S=\{s_{1} ,s_{2} ,\dotsc ,s_{n}\}$ places. Each unordered pair of places has cost and gain: $\displaystyle c\{s_{i} ,s_{j}\} \in \mathbb{N}$, $\displaystyle g\...
0
votes
1answer
20 views

Given N positive integers are they the integers 1-N : What is the relationship between this problem and NP?

Here’s the decision problem: Suppose I have N positive integers encoded in base-2 (as oppose to unary) Are these integers precisely the integers 1-N in some order? This is related to the Hamiltonian ...
0
votes
1answer
268 views

Could the empty language be NP-Complete?

I think the empty language is NP but I'm not sure if it is NP-Complete
-1
votes
1answer
45 views

Is clause learning in SAT parsimonius?

I have a model counting program bob. On some graph coloring formulas, bob got the right answer only after removing clause learning. That is to say, with clause learning, bob sometimes counts ...
1
vote
0answers
96 views

NP-completeness of SHIP LOADING

I need some help with the following question. SHIP LOADING: Given items of weights $x_1,\dots,x_n$, ships of weight capacity $B$, can the items be loaded onto $C$ or fewer ships? (All numbers are ...
0
votes
1answer
27 views

Are problems that are fractions of constraints of NP-complete problems also NP-complete?

We know that Hamiltonian path, clique and independent sets are NP-complete but what about half or the square root of each problem or a fraction of $n$ ? That is, for a graph, $G$ of $n$ nodes, is ...
1
vote
1answer
113 views

$P = NP$, what am I missing?

First post here so hope I'm not missing too many guidelines. I've had this idea for a few weeks now and I can't myself see where I'm going wrong with it, hope it makes some sense to you and thanks in ...
0
votes
1answer
90 views

If P = NP, do these NP-complete problems reduce to these specific easier versions?

I am trying to understand reductions and NP-completeness from Algorithms by Dasgupta et al. Chapter 8 has the table below and I am wondering: if $P = NP$ does each of the problems on the left reduce ...
1
vote
0answers
81 views

Proving B-Min-Cost Strongly connected Subgraph is NP-Complete

We have a strongly connected directed graph where each edge has positive integer weights. We are also given a $B \in \mathbb{N}$. Does there exist a strongly connected subgraph where sum of edge ...
0
votes
1answer
45 views

Is $\Pi’\propto_{poly}\Pi$ for any two NP-complete problems $\Pi,\Pi'$?

I am facing the following question: Let $\Pi$ and $\Pi$’ be two NP-complete problems, prove or refute $\Pi’\propto_{poly}\Pi$. I do not understand the meaning of this question and how to answer it. ...
2
votes
1answer
184 views

How is this reduction of 3-SAT to Half-SAT not valid? [duplicate]

I am studying algorithms and there is a question in CLRS called the Half-SAT problem We are given a 3-CNF formula with n variables and m clauses where m is even. We wish to determine whether there ...
0
votes
1answer
51 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: Edit: And missing from the pic as @Nathaniel points out in his answer below: "...
1
vote
1answer
88 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 ...
4
votes
1answer
36 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
142 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
56 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
115 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
41 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
190 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
17 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
26 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
128 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
133 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
39 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),...
2
votes
0answers
54 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
72 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
47 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
31 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
39 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
41 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
66 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
41 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
62 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 ...
27
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 ...
-3
votes
1answer
46 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
73 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
42 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
73 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
82 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
283 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?

1 2
3
4 5
29