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
0answers
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 ...
0
votes
0answers
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 ...
1
vote
2answers
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?
0
votes
0answers
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 ...
1
vote
0answers
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 ...
2
votes
0answers
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 ...
-1
votes
1answer
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 ...
0
votes
3answers
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 ...
0
votes
1answer
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 ...
7
votes
1answer
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$. ...
0
votes
0answers
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. ...
1
vote
1answer
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, ...
4
votes
1answer
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
1
vote
7answers
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 ...
0
votes
1answer
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$, ...
1
vote
1answer
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{...
2
votes
1answer
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 ...
1
vote
2answers
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 ...
6
votes
0answers
518 views

What could we say about that conjecture that yields P != NP?

Let $F$ be the set of all Boolean formulae. We say that a Boolean formula $\varphi$ is positive (=monotone) if $\forall \alpha\in F,i\leq n$, if $\alpha\wedge\neg x_i\models\varphi$, then $\alpha\...
0
votes
1answer
41 views

Why we can't have some algorithm to be polynomial if there are generic conditions that make them so?

I explain it better: There are some algorithms that is clearly in NP, also NP-complete, but that under certain conditions they can be solved in polynomial time. An example is Bin Packing, the decision ...
6
votes
1answer
138 views

Is “Solving two-variable quadratic polynomials over the Integers” is an NP-Complete Problem?

On this Wikipedia article, they claim that given $A, B, C \geq 0, \; \in \mathbb{Z}$, deciding whether there exist $x, \,y \geq 0, \, \in \mathbb{Z}$ such that $Ax^2+By-C=0$ is NP-complete? Given by ...
0
votes
1answer
16 views

Multi-dimensional Knapsack with Minimum Value constraints for Dimensions

In MDK, we have a vector $W = \{W_1, W_2, ..., W_d\}$ where each element corresponds to the maximum weight for the respective dimension in the knapsack. I want to add a conditional constraint: $V = {...
8
votes
0answers
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$? ...
2
votes
1answer
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 ...
-1
votes
3answers
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 ...
2
votes
1answer
84 views

Complexity of specific cases of MAX2SAT

I know that MAX2SAT is NP-complete in general but I'm wondering about if certain restricted cases are known to be in P. Certainly the languages $L_k:=\{ \phi \,|\, \phi\,\text{is an instance of 2SAT ...
3
votes
1answer
39 views

Is MAX-averageSAT a well-known problem?

Is there any variant of the Boolean SAT or Max-SAT problem that has a flavor of maximizing or minimizing the average of the weights of the satisfied clauses of a WCNF formula? Any literature on an ...
0
votes
3answers
417 views

Greedy algorithm for vertex cover

Given a graph $G(V, E)$, consider the following algorithm: Let $d$ be the minimum vertex degree of the graph (ignore vertices with degree 0, so that $d\geq 1$) Let $v$ be one of the vertices with ...
0
votes
1answer
45 views

NP-Complete Problem and Polynomial Hierarchy

I have tried to search the internet to check if the following is correct: If $\sum_{2}$ contains a NP-Complete problem then PH collapses to NP: $PH=NP$ For example if $SAT\epsilon\sum_{2}$ than: $PH=...
-2
votes
1answer
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)?
0
votes
2answers
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 ...
0
votes
0answers
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 ...
0
votes
2answers
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 ...
0
votes
2answers
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 ...
2
votes
0answers
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$ ...
1
vote
0answers
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 ...
0
votes
1answer
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-...
1
vote
1answer
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....
2
votes
2answers
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 ... ...
1
vote
0answers
52 views

Finding $l$ subsets such that their intersection has less or equal than $k$ elements NP-complete or in P?

I have a set $M$, subsets $L_1,...,L_m$ and natural numbers $k,l\leq m$. The problem is: Are there $l$ unique indices $1\leq i_1,...,i_l\leq m$, such that $\hspace{5cm}\left|\bigcap_{j=1}^{l} L_{i_{j}}...
0
votes
2answers
16 views

Proof of Co-Problem being in NP if Problem is in NP using negated output

Given any problem $P$ that we know of being in $NP-\text{complete}$, where is the flaw in the following proof? Given a problem $Co-P$ which is the co-problem of $P \in NP-\text{complete}$, $Co-P$ is ...
7
votes
1answer
248 views

Is the buckets of water problem in NP?

Continuing from this question: the buckets of water problem. (All the definitions can be found there, so I will not repeat them). As seen there by Yuval's answer, the problem is NP-Hard. I was ...
5
votes
2answers
253 views

Graph coloring variation

Are there variations of the classic graph coloring problem that the number of neighbors in the same color is limited but not zero (in the original problem the limit is zero)? Problem: Given a graph $G$...
2
votes
1answer
177 views

Proof for NP-hardness of simultaneous minimization and maximization of a weighted subset

I am working on a problem defined as the following Given a set of $n$ elements called $R \subseteq \mathbb{N} \times \mathbb{N}$ and numbers $Z,G \in \mathbb{N}$, where $Z$ is a measure of our ...
1
vote
1answer
33 views

Do any single-cell organisms exist that approximate NP-hard problems within a factor better than $1/2$ $log$2?

I've seen on Wikipedia; that set covering cannot be approximated in polynomial time to within a factor mentioned above. Unless $NP$ has quasipoly-time algorithms. Now, this must pertain to classical ...
0
votes
1answer
21 views

Pick elements that don't exhaust any set

The following is an NP-Complete problem: Suppose you have a collection $\mathcal{C}$ of sets, so that $A_i\in \mathcal{C}$ and $A_i$ is some set--we can suppose the elements of $A_i$ are integers. ...
0
votes
1answer
22 views

reduction of independence problem and cluster problem

independent problem is: there is a simple and undirected graph, we are looking for the maximum vertex in which there is no edge between any two of them. cluster problem is: there is a simple and ...

1
2 3 4 5
25