# 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,464 questions
Filter by
Sorted by
Tagged with
40 views

### Can these variants of SAT/Tautology be actually pretty simple?

There are 8 (very similiar) languages I'd like to discuss here: CNF SAT DNF SAT CNF No-SAT (Existence of a false assignment) DNF No-SAT CNF Tautology DNF Tautology CNF Contradiction DNF Contradiction ...
27 views

### Is there a non-deterministic polynomial time TM such that $L(M)\in NPC$ and $L(\bar M) \in NPC$?

When $\bar M$ is a non-deterministic polynomial time TM with final states switched: accept to reject and vice versa.
• 1
25 views

### Can you help me find some examples of 3co-SAT for 4 variables?

I've been studying the examples of 3co-SAT recently. It's easy to find an example of one variable. $(x_1\lor x_1\lor x_1)\land (\overline{x_1}\lor \overline{x_1}\lor \overline{x_1})$ Examples of 2 ...
• 153
34 views

### Why don't we consider that NP = co-NP while we can reduce Tautology problem into Satisfiability in polynomail time easily?

Let's determine if an expression is tautological or not and let's try this expression: ((a ⊼ b) ∨ c) ↔ (¬a ∨ ¬b ∨ c). We can turn this problem into CIRCUIT-SAT decision problem by asking if the ...
11 views

### CNF-SAT time complexity and input processing

Boolean Satisfiability (CNF-SAT) problem in $n$ variables may contain a CNF formula with $O(2^n)$ clauses in the worst case. My question is: Wouldn't a program reading a CNF formula have to ...
• 103
1 vote
34 views

### Identifying easy subsets/instances of NP-hard problems?

Say I want to solve a set of problems. I know that I can map my problem as a problem that is known to be hard in the general case (say, inference in Bayesian networks). But my set only contains ...
• 241
72 views

### 2-Satisfiability is NP Complete, isn't it?

To show that any formal language is NP Complete first it must be showed that this formal language is both in NP and NP Hard. So to show that 2-Satisfiability is NP Complete first it must be showed ...
57 views

### Exact Cover variant: partition a family of subsets into exact coverings

I have found that a problem that I'm analyzing is equivalent to the following variant of the Exact Cover problem: Partition into $k$ Exact Covers Input: A universe ...
• 111
49 views

1 vote
56 views

### Is Set Cover problem with subsets of size ≤2 solvable in polynomial time?

I came across the below question where the polynomial time solution to the "Set Cover Problem" is discussed when the subsets are of size EXACTLY 2. Set cover problem with sets of size 2 The ...
27 views

1 vote
77 views

### With fixed k>=4, can 3-coloring in a graph of vertex degree at most k be solved in polynomial time?

I couldn't think of a poly-time solution. Moreover, I think that there is a pretty simple Karp-reduction from 3-coloring problem, which is NP-complete. let's say that graph G is in 3-colloring. I'll ...
45 views

The load balancing problem: Given we have $m\ge3$ machines (servers) $M_{1}, M_{2},\dots,M_{m}$. As input we are given $n$ jobs defined by their processing times: $t_{1},t_{2},\dots,t_{n}\in\mathbb{Q}... • 49 1 vote 2 answers 471 views ### Prove that a quadratically-constrained linear program (QCLP) is NP-Complete Show that if we strengthen linear programming by also allowing constraints of the form $$\sum_{i,j = 1}^n a_{ij} x_i x_j = b,$$ for integers$b$and$a_{ij}$, then the problem becomes NP-complete. ... • 113 2 votes 0 answers 37 views ### scheduling with profits and deadlines clrs The following problem is on page 1104 of the CLRS textbook: I was wondering how to show that the problem is NP-hard (i.e. part b)? Like subset-sum, this problem is weakly NP-complete; it has a ... 2 votes 1 answer 29 views ### a generalized job assignment problem The following problem is from a past algorithms course exam and I'm using it to test my knowledge. There are m machines and n jobs. Each machine can doing a subset of jobs. Each machine i has a ... 0 votes 0 answers 44 views ### Prove minimum vertex bisection problem is reducible from bisection width, thereby proving NP-Completeness The bisection width problem gives you a yes or a no -> if there exists a bisection of size at most$K$for$G=V,E$. Minimum Vertex Bisection problem gives you a bisection of the smallest size. ... 0 votes 1 answer 43 views ### Is there a polynomial time reduction from B to A in this case? Suppose we have an NP-complete problem A, an NP-hard problem B, and a polynomial time reduction from A to B exists. Do we have a polynomial time reduction from B to A as a result? 0 votes 2 answers 37 views ### Post Correspondence Problem is undecidable I am reading Introduction to the Theory of Computation by Michael Sipser and I am in chapter 5. It says here that the Post Correspondence Problem is undecidable, but thinking about it, given a ... 0 votes 0 answers 31 views ### NP Completness and NP Hard i need some help regaridng this text: CLIQUE = { G, k | G is an undirected graph that contains a clique with k nodes } The textbook proves that CLIQUE is NP-complete. Define the language TWO-CLIQUES ... • 13 0 votes 1 answer 136 views ### If A reduces to B and B reduces to C, does that mean A reduces to C? If A is in the class P, B is NP-complete, and C is not in the class NP. And A reduces to B and B reduces to C. Which statements are true? A is in the class NP. A reduces to C. If S is a candidate ... • 103 2 votes 1 answer 47 views ### Is the weighted sum of subset prefix product problem NP-hard? I have this strange problem where we have a set of positive numbers$M$, a fixed number$n$, and a function$f\colon M \rightarrow R^+$mapping each number in$M$to another positive number. We want ... 1 vote 0 answers 23 views ### Assumptions needed by Exact Cover by 3-Sets (X3C) The problem is defined as https://npcomplete.owu.edu/2014/06/10/exact-cover-by-3-sets/: Given a set$X$, with$|X| = 3q$(so, the size of$X$is a multiple of$3$), and a collection$C=\{(x_{i1},x_{...
• 65
1 vote
174 views

Say we have bit mask with some bits on and off: 1001110010101 We want to "deduce pattern", by covering this mask with as few strided masks as possible. ...
42 views

### Programmatically determine if a tie is possible in US elections

Problem 3.5 from book: "Algorithms for interviews". There are 51 states (+ Washington DC), each with different amount of votes. Find the number of votes of each state here Suppose there are ...
• 123
26 views

### Why do we promote Ubiquitous Computing when there are problems out there that cannot be solved computationally?

According to Alan Turing, there are 2 types of problems i.e. NP Complete and non-NP Complete, then why do we promote Ubiquitous Computing and introducing sensors and embedded systems into our daily ...
• 299
20 views

### Algorithm for Wrapping Problem

Assume we have n items with each having a different length and m wrappers each has a different length. The cost of every wrapper is proportional to its length. An item can be covered with one or more ...
105 views

### Proof that Balanced Partition is NP-complete

In the Balanced Partition problem, there are $2m$ nonnegative integers with sum $2s$. The goal is to decide whether they can be partitioned into two subsets of $m$ integers and sum $s$. The problem is ...
• 5,704
1 vote
46 views

### Solution methods for this Weighted Partial Set Cover-ish problem

Given a set of subsets $S_1, ..., S_N$ of a finite universe $E$ of elements $e_1, ..., e_n$ and mapping of those elements to an integer 'weight' $w_1, ... w_n$, select the subset of subsets which ...
• 183
57 views

### What is the name for this minimal satisfying set covering problem? [duplicate]

Preface Hello! I have a problem here that's difficult for me to Google, and I don't know if there's a name for it. It feels like a set cover problem of some kind, but I'm very unfamiliar with ...
34 views

### Subclass of problems of an NP hard problem

I have an NP hard problem $P$ that takes in arbitrary $G = (V, E)$ as input. I have another problem $Q$ that I want to show is NP hard, and this problem has arbitrary complete graphs $G'$ as input. Is ...
• 151
38 views

### Deciding whether there always exist k different disjoint paths between any pair of vertices in a graph

Given a graph $G$ and an integer $k$, is it NP-complete to decide whether there always exist $k$ different disjoint paths between any pair of vertices of $G$?
78 views

### most cost-effective route w.r.t. gas in a labelled graph

Consider a car that can hold gas to travel a distance of $c \in N$ kilometers (its capacity) on a full tank that's initially empty. The car starts in node $s \in V$ of a graph. Each vertex $V_i$ of ...
• 2,376
1 vote