# 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.

1,237 questions
Filter by
Sorted by
Tagged with
20 views

### Set partition with an allowable difference

I have a variation of the partition problem, which is to partition the multiset S into two subsets S1, S2 such that the difference between the sum of elements in S1 and the sum of elements in S2 is ...
16 views

### 3-OCC-MAX SAT np-complete?

Assuming 3-OCC-MAX SAT is the language of all CNF formulas in which every variable appears in at most 3 clauses. Is this problem NP-Complete? I'm trying to find a karp reduction between SAT and this ...
197 views

### NP-completeness of testing whether a SAT formula does not contain any redundant clause

This paper explains that testing the irredundancy of a SAT instance is NP-complete. But I don't understand the theorem/reduction. How would one reduce 3SAT or k-SAT to this problem, for example?
51 views

### 4SAT $\leq_p$ NAE4SAT

Given the SAT problem, the NAE (not all equal) SAT adds the restriction that there must exist two literals in a clause which have different truth values in a satisfying assignment. We can show that ...
28 views

### Is Partition Problem with non-integer input NP-complete?

The Partition Problem supposes that we have a set $S=\{s_{i} \in \mathbb{R^{+}}\}_{i=1}^{n}$, is there a subset $T$ such that $\sum_{s \in T} s = \sum_{s \notin T}s$? I have read a lot of proofs using ...
36 views

### Examples of exponential time linear space exact algorithms

I am looking for examples of NP-complete problem-solving exact algorithms with a linear space complexity and an exponential time complexity. Algorithms which solve the k-SAT problem exactly (such as ...
24 views

### What are the practical examples of Semidecidable problems? Is NP problem a semidecidable problem?

I am going through a Turing machine topic. I know about decidable, semi decidable, and decidable problems. But honestly speaking, I did not get any practical examples of Semidecidable problems. Can ...
82 views

### Is the fastest solution for one NP-Complete problem the fastest solution for all NP-complete problems?

This answer seems incorrect to me: Which NP-Complete problem has the fastest known algorithm? The fastest solution for one NP-Complete problem should be the fastest solution for all NP-Complete ...
34 views

### If a poly-time solution exists for an NP-Complete (Decision) problem, then there exists a poly-time solution for the NP-hard (Optimization) flavor?

This question boils down to: If a polynomial time solution exists for a decision problem, is there also a polynomial time solution for the same problems optimization flavor? Let's take the Traveling ...
197 views

### Polynomial time algorithm for finding a maximal monotone subset

Input: Some fixed $k>1$, vectors $x_i,y_i\in\mathbb R^k$ for $1\le i\le n$. Output: A subset $I\subset\{1,\dots,n\}$ of maximal size such that $(x_i-x_j)^T(y_i-y_j) \ge 0$ for all $i,j\in I$. ...
19 views

### How to prove the complexity of this modified version of the minimum dominating set problem?

I have an optimization problem and I want to show its complexity. The optimization problem is the same as the minimum dominating set problem, but with an additional constraint. The constraint is easy. ...
38 views

### Why does SAT-UNSAT $\in NP \implies NP = coNP$

I was reading this post about the DP completeness of the problem SAT-UNSAT (both are well defined in this post). The answer added a note at the end that states the class complexity DP differs from NP, ...
47 views

### Can quantum computing help solve NP-Complete problems?

i was just wondering if quantum computing has done any good so far in solving NP complete problems. I am aware that quantum computing does solve some NP problems which are classically hard in ...
58 views

### Is it true that if you solve an NP-complete problem in non-polynomial time, the solution also solves other NP-complete problems as well?

This relates to an answer for this question. The opinion said that: Personally, I don’t see much value in coding interviews. The problems I’ve seen asked as coding questions have been (for the most ...
42 views

### 3SAT and directed graph

Given a 3SAT instance (a Boolean expression in three conjunctural normal form), we draw a directed graph, where for each Boolean variable $x_{i}$ we have the nodes $x_{i}$ and $!x_{i}$; for each ...
27 views

### What is the complexity of k-clique problem with a predetermined vertex in the solution?

Clique (from WikiPedia): Clique is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent; that is, its induced subgraph is complete. K-Clique ...
3k views

### Why can't we say that a Neural Network is a NP problem solver?

From this video lecture from MIT https://youtu.be/moPtwq_cVH8?t=1229 there is mention how NP complexity works with finding a "lucky" algorithm and luck can never be accounted for. The ...
45 views

### How can you modify a SUBSET-SUM instance so evaluating a set outputs either 0 or 1?

An SUBSET-SUM instance is a list of $n$ integers $\{ a_1, a_2,... a_n\}$. To evaluate a subset is to output the sum of a subset. However, I want to know, is it possible to create a new instance $T$, ...
22 views

### Reduction from VC to {a,k | a is a 3DNF (disjunctive normal form) and there exists an assignment satisfying exactly k clauses in a}

I have the following question : \begin{align} L_2 = \{a,k\ \mid \text{ a is a 3DNF (disjunctive normal form) and} \\ \text{there exists an assignment $z$ satisfying exactly $k$ clauses in }a\} \end{...
21 views

### Is CMCG (Constrained Maximum-Weight Connected Graph) problem NP-complete?

MCG Problem: Consider a positive integer R and an undirected graph G = (V, E), in which each vertex is assigned a weight (or value). The maximum-weight connected graph (MCG) problem is to find a ...
125 views

### NP-completeness of a Generalized Version of Subset Sum

I am curious about the NP-completeness (or if not, an efficient algorithm) for the following generalization of the subset sum problem: In subset sum, we are given a number $t$ and a collection $S$ of ...
518 views

141 views

### Complexity of finding a Eulerian path such that the image under a bijection is also a Eulerian path

Problem input: undirected graphs $G$, $H$ and a bijection $f: E(G) \to E(H)$ Question: Is there a Eulerian path $p: \{1,\dots,|E(G)|\} \to E(G)$ in $G$ such that $f \circ p$ is a Eulerian path in $H$? ...
32 views

### Approximation factor preserving reduction

The definition of approximation factor preserving reduction from the book by Vijay V. Vazirani, page 365: Let $\Pi_1$ and $\Pi_2$ be two minimization problems, an approximation factor preserving ...
165 views

### Why don't passwords prove P != NP?

Pardon my ignorance on the matter but, Verifying passwords = Polynomial (linear) Guessing passwords = Exponential Since each guess has nothing to do with one another, exponential time is best possible ...
84 views

69 views

### Can an NP-Complete problem be reduced to an NP problem?

All NP problems can be reduced to NP-Complete problems, can an NP-Complete problem be reduced to a NP problem (non complete)?
47 views

### Complexity of Subset Sum where the size of the subset is specified

I know it should be easy but I'm trying to determine the complexity of the following variant of Subset Sum. Given a subset $S$ of positive integers and integers $k>0$ and $N>0$, is there a ...
47 views

### Is a or free SAT formula NP complete?

Let $L$ be the languague which contains all satisfiable formulas which do not have the or symbol $\lor$. Or more precise L=\{\phi | \phi \text{ is a satisfable formula which is only using the ...
76 views

### If we prove that there is an NP-complete problem that is P, Can we consider that P=NP?

I discover this in All NP problems reduce to NP-complete problems: so how can NP problems not be NP-complete? If problem B is in P and A reduces to B, then problem A is in P. Problem B is NP-complete ...
61 views

### Confusion in Reduction of Hamiltonian-Path to Hamiltonian-Cycle

The following is an excerpt from a material on NP-Theory: "Let G be an undirected graph and let s and t be vertices in G. A Hamiltonian path in G is a path from s to t using edges of G, on which ...
29 views

### Reducing Dominant Set Problem to SAT

I am trying to solve a problem and I am really struggling, I would appreciate any help. Given a graph $G$ and an integer $k$ , recognize whether $G$ contains dominating set $X$ with no more than $k$ ...
68 views

### Greedy Probabilistic Algorithm for $Exact$ $Three$ $Cover$

I have a probabilistic greedy algorithm for Exact Three Cover. I doubt it'll work on all inputs in polytime. Because the algorithm does not run $2^n$ time. I will assume that it works for some but not ...
36 views

### If A is polynomial-time reducible to B and B is NP-Complete, can I say that A is NP-Complete as well?

I searched a lot on internet, including here, but I couldn't find an explanation that could convince me. The problem is the same of the title, if A is polynomial-time reducible to B and B is NP-...
85 views

### Is Monotone 3-SAT with exactly 3 distinct variables untractable?

I have given the following SAT variation: Given a formula F in CNF where each clause C has exactly 3 distinct literals and for each C in F either all literals are positive or all literals are negated....
114 views

### Is it possible to train a neural network to solve NP-complete problems?

I'm sorry if the question is not relevant, i have tried to search for articles about it but i couldn't find satisfying answers. I'm starting to learn about machine learning, neural networks etc ... ...