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
-4
votes
0answers
53 views

Are approximations to $#P$ gibberish? [closed]

approximations to #P are gibberish the model count in satisfiability (#P) implies straightforward access to a vast empire inside the logic of truth including N Boolean variables in a formula with N ...
3
votes
0answers
30 views

Reduction from Edge-Coloring and Vertex-Coloring to a new problem

I have a question from a test I did and failed, a question I failed to do. In short: the question is about reduction from Vertex-coloring and Edge-coloring, to a new problem they have defined. The new ...
-4
votes
3answers
76 views

What is wrong with this argument that if A is NP Complete, but B is in P, then A\B is NP Complete and B\A is NP Complete as well?

The following seems to me to be relevant to this question, but to me is an interesting exercise, especially since I have not formally worked with complexity before, but I want to learn more: Suppose ...
-1
votes
1answer
32 views

Reducing subsetsum to {<G, l, u> | G is a weighted graph that has a spanning tree with weight between l and u}

How can I reduce Subsetsum (or maybe other np-complete problem) problem to the problem below? input : a weighted graph $G$ and numbers $l$ and $u$. output : Does $G$ has spanning tree, $S$, such that $...
2
votes
1answer
33 views

Language in NPC and CoNP

A few days ago I had a test that I failed to pass, and it had a question that I failed to do. the question: given: $A \in NPC$ $A \in CoNP$ Determine which of the following statements is correct: $P\...
3
votes
2answers
50 views

Reduction with CoNP and CoNPC

I have a question I was unable to do, from a last test I had. This is the question: Suppose that there is a language $A \neq \emptyset ,\sum{_{}}^{*}$ such that $A \in CoNP - CoNPC$. Determine ...
2
votes
1answer
21 views

Reduction with NPH

I have a question in complexities that I could not do. There will be D, E, F, three languages belonging to NPH. Suppose that the reductions exist $D \leq _P E$ and $E \leq _P F$. Determine which of ...
-1
votes
1answer
34 views

Reduction from SAT to 3SAT

a few days ago I had a test and could not pass it. This is a question I did not understand in the test. Recall the reduction we saw $SAT \leq _p 3SAT$. Given verse $\varphi$ in the form of $CNF$, we ...
1
vote
2answers
121 views

Reduction from vertex-coloring problem to edge-coloring problem

A few days ago I had a test and could not pass it. This is a question I did not understand in the test. We will look at the Edge-Coloring problem, in which, as is well known, we get as input graph G =...
1
vote
1answer
34 views

Why this problem is NP-Hard?

I'm asking about the question described here: Knapsack Problem with exact required item number constraint Can't we iterate over $\binom{n}{L}$ options (which is polynomial), and for each option check ...
3
votes
1answer
46 views

FPT algorithm for Knapsack

I tried to search whether Knapsack (the decision version) has a FPT algorithm, but didn't find anything on the topic. Can someone help with a reference?
1
vote
0answers
22 views

Research on exact-cover problem and graph theory for NP-complete problems? [closed]

Sorry for the vagueness, but I'm trying to study the latest progress on the exact cover problem and using graphs for NP-complete problems. Googling around has not been very helpful. I understand the ...
0
votes
1answer
36 views

Is this variation of Max-Coverage NP-hard?

Setup An instance of Max-Coverage is typically defined by a collection of $n$ sets $S = \{s_1, s_2, \dots, s_n\}$, and a budget $k$, where the objective is to select a subset $U\subset S$ such that $$\...
-5
votes
0answers
56 views

VS Problem algorithm

In CLOSED VERTEX COVER, we are given a graph G In CLOSED VERTEX COVER, we are given a graph 𝐺 where each vertex π‘£βˆˆπ‘‰(𝐺) has self-utility π‘’π‘£βˆˆβ„• and self-pollution π‘π‘£βˆˆβ„•, and π‘˜,π‘ˆβ‹†,π‘ƒβ‹†βˆˆβ„•. For each ...
0
votes
0answers
18 views

Polynomial Reduction from $3SAT$ to $MSAT$

I am supposed to show that $3SAT$ $\rightarrow$ Every clause hast exact $3$ literals is polynomial reducible to $MSAT$ $\rightarrow$ At least half of every clauses' literals are true Let $F$ be a ...
0
votes
0answers
79 views

Algorithm for Variant of 0-1 Knapsack Problem

Variant of 0-1 Knapsack Problem is when you can choose exactly $k$ items from $n$ items, and $k$ is positive integer parameter that came in the input. Is there an algorithm with running time ...
-2
votes
0answers
142 views

Is there exist FPT algorithm for a variant of VC problem?

In CLOSED VERTEX COVER, we are given a graph $G$ where each vertex $v \in V(G)$ has self-utility $u_{v} \in \mathbb{N}$ and self-pollution $p_{v} \in \mathbb{N}$, and $k, U^{\star}, P^{\star} \in \...
2
votes
1answer
46 views

Number of queries for $NP^{NP}$

So a few days ago my lecturer told us that for every nondeterministic polynomial time oracle machine $M$, there is a nondeterministic polynomial time oracle machine $N$ that gives us $L(N^{3-SAT}) = L(...
0
votes
1answer
40 views

How to prove Dense Subgraph problem is in NP

I have been studying NP-Complete problems and I saw the Dense Subgraph problem. Then I saw that they are trying to show that the problem is NP (see below quote), but I can't understand how it verifies ...
1
vote
3answers
91 views

Spanning tree whose sum of edge weights are between two boundries

I saw this problem: $\langle G,w,k_1,k_2 \rangle \in L$ iff Graph $G$ has a spanning tree whose sum of edge wights are less than $k_2$ and greater than $k_1$. The problem says that we can prove this ...
1
vote
1answer
25 views

Computational complexity of dividing a set of constraints into a minimum number of satisfiable clusters

I am looking for the computational complexity of the following problem. Divide a given set of constraints into a minimum number of satisfiable clusters such that the constraints within the same ...
0
votes
1answer
21 views

Efficient structure for pruning on job scheduling

This is an issue I encountered on several applications with different variants. But here is the common base for which I suspect to miss a more efficient approach. There are $K$ different tasks to ...
3
votes
0answers
38 views

NP-complete problem

Is the following line true? Consider three problems A, B and C. If $A$ $<p$ $B$ and $B$ $<p$ $C$ and $B$ is NP-complete problem, then $C$ is also NP-complete. If B is NP-complete, then C would ...
1
vote
1answer
24 views

Time complexity of the triangle factoring problem

We define the triangle factoring problem as in Triangle Factors in Random Graphs, which is, given a simple undirected graph of $3n$ nodes, find if there's a subset of edges dividing vertices into $n$ ...
0
votes
2answers
80 views

Minimum number of moves puzzle

Let K players be among N towns in a circular position. On each turn, only one player can move. A player cannot move if he is the one who moved in the previous turn. A player can only move clockwise ...
2
votes
1answer
59 views

Must all NP-complete problems have an asymptotically optimal algorithm?

According to Blum's speedup theorem, there exist problems with no asymptotically optimal algorithm. Suppose that NP-complete problems had speedup. We know a problem X with asymptotically time ...
0
votes
1answer
31 views

NP-completeness of variant SAT: SAT-5Clauses

I'm solving Problem 14.4 of What can be computed?. 14.4 Define the decision problem SAT-5CLAUSES as follows. The input is a Boolean formula B in CNF. The solution is β€œyes” if it is possible to ...
2
votes
0answers
76 views

An unknown combinatorial optimization problem

I have $N$ available sensors and $M$ devices. Each device needs $a$ sensors. One sensor cannot be used on multiple devices. Each sensor has two properties defined by $H$ and $R$. Let $\sigma_{i\_H}$ ...
1
vote
1answer
31 views

Is every pair of NP-Complete problems reduced in polynomial time?

As shown above, several NP-Complete problems are derived from GSAT (general satisfiability problem) by a polynomial-time reduction. Then, my question is that is every pair of NP-Complete problems ...
0
votes
0answers
39 views

Is this combinatorial seach problem NP-complete?

The context: Consider the following optimization problem. Let $f_1,\dots,f_L:\mathbb{R}\to\mathbb{R}$ arbitrary (continous) functions for $L>1$ and $x_k\in\mathbb{R}$ evolve according to $$ x_{k+1}...
0
votes
1answer
69 views

Assume P != NP, are these assertions valid?

Assume $P \ne NP$, and $A$ is a problem in $P$ and $B$ is a problem which is $NP-complete$. Are the following assertions valid? $A \le_{P} B$ $B \le_{P} A$ My approach: $B \le_{P} A$ isn't valid, ...
1
vote
1answer
25 views

Solving a problem with instance of size $n$ in $O(n)$

Today I read the following text in CLRS: We say that an algorithm solves a concrete problem in time $O(T(n))$ if, when it is provided a problem instance $i$ of length $n = |i|$, the algorithm can ...
2
votes
0answers
32 views

Sub-graph Selection Algorithm Problem (Dynamic Programming or NP)

We have an algorithm problem in hand, can you please write your ideas about this, thank you! There are N many nodes with K different colors. Some of the nodes have direct connection between each other ...
3
votes
1answer
100 views

NP completeness of deciding whether a set of examples, consisting of strings and states, has a corresponding DFA?

I'm working on a textbook problem, 7.36 in Sipser 3rd edition. It claims that if we are given an integer $N$ and set of pairs $(s_i, q_i)$, where $s_i$ are binary strings and $q_i$ are states (we are ...
1
vote
1answer
16 views

why does the poly-time reduction from dominating set to vertex cover require adding a vertex to every edge?

I'm trying to understand a poly-time reduction proof from dominating set to vertex cover. If I'm understanding correctly, it goes something like this: suppose we have a vertex cover of size $k$ in ...
1
vote
1answer
42 views

How to prove NP-hardness of a Hamiltonian Path problem by reducing longest-path problem?

I know how to prove longest-path problem by reducing Hamiltonian Path problem. Here I want to prove NP-hardness of a Hamiltonion Path problem by reducing longest-path problem. (pretend we know longest-...
1
vote
1answer
135 views

Proof of NP-completeness via extra information

I have a set of multisets $S = \{ X_1, \dots, X_K\}$ where $X_i \subset \mathbb{R}$. I need to find an optimal partition $L^*, R^*$ such that this $E(L) + E(R)$ is minimized. Denote $K(X) = \cup_{I \...
0
votes
1answer
47 views

The subset sum problem is not in P because the question is about lossy compressed data? Why not?

Where is there a gap or error in my reasoning? The subset sum problem deals with a set of n numbers, which is the result of lossy compression of an array r of numbers (r = (2^n)-1). The compression ...
-2
votes
1answer
46 views

Reduction from 3SAT to SUBSET-SUM

The reduction from 3SAT to SUBSET-SUM includes building a table as follows: Where base 10 representation is used for the rows in the table. I would like to know if the reduction will still be correct ...
0
votes
1answer
35 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
25 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
32 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
47 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
76 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
40 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
49 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
29 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 ...
2
votes
1answer
80 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
19 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 ...

1
2 3 4 5
…
28