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
0 answers
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 ...
user avatar
-1 votes
0 answers
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.
user avatar
  • 1
0 votes
1 answer
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 ...
user avatar
  • 153
0 votes
0 answers
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 ...
user avatar
0 votes
1 answer
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 ...
user avatar
  • 103
1 vote
1 answer
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 ...
user avatar
  • 241
-4 votes
0 answers
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 ...
user avatar
2 votes
0 answers
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 ...
user avatar
  • 111
2 votes
1 answer
49 views

Is this special case of the subset-product problem $\mathsf{NP}$-complete?

It is a well known fact that the following 'subset-product' problem is $\mathsf{NP}$-complete when $n/\log M \in \Theta(1)$. Consider a size-$n$ subset of a multiplicative group $\mathbb{G}\cong\...
user avatar
0 votes
2 answers
38 views

Are all np-complete problems also np-hard?

Are all np-complete problems also np-hard? In other words, is np-complete a subset of np-hard? I don't think it is entirely clear from the illsutration below, so I just wanted to quickly ask to ask to ...
user avatar
0 votes
0 answers
62 views

Horn 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 Horn Satisfiability is NP Complete first it must be showed ...
user avatar
0 votes
2 answers
74 views

If P=NP, are all P problems NP-complete?

In my understanding, if we could prove one of the NP-complete problems is a P problem, then all of the NP problems are P problems. Because P problems are NP problems and NP problems are P problems, P=...
user avatar
  • 1
0 votes
2 answers
55 views

How could NP-complete problems be in P?

I've learned some basics about P and NP. Please excuse if the following is not very precise. I've read that NP-complete problems are the hardest problems in NP. (Is that correct?) But now I'm ...
user avatar
  • 140
2 votes
1 answer
50 views

Solving efficiently NP problems with infinite precision

I heard a few times that if we allow computations with infinite precision, we could have unrealistic powers of computation up to the point of solving NP problems efficiently. Is it true? If yes: what ...
user avatar
2 votes
1 answer
121 views

Complexity of the (Complete/Assign) 3-SAT problem?

A complete $k$-CNF formula on $n$ variables $(k\le n)$ is a $k$-CNF formula which contains all clauses of width $k$ or lower it implies. Let us define the (Complete/Assign) 3-SAT problem: Given $F$, a ...
user avatar
1 vote
1 answer
79 views

Covering all colors with unit intervals

Suppose we are given $n$ points on the real line, where each point is colored with a color from set $C=\{c_1,c_2,\ldots,c_k\}$ that contains $k$ distinct colors. We try to cover the $k$ distinct ...
user avatar
  • 11
0 votes
0 answers
41 views

I need to show that the problem is NP-complete

Double-SAT = {𝜓: 𝜓 has at least two satisfying truth assignments}. Hint: reduce from SAT. Start with a formula 𝜑 and modify it to get a formula 𝜓 so that 𝜑 is satisfibale if and only if 𝜓 has at ...
user avatar
  • 11
0 votes
0 answers
8 views

connection between self reducibilty and the hardness of the dicison problem

If given that a search problem R is self-reducible, thus we can solve it in polytime steps by (the optional ability of) asking its corresponding decision problem Sr, can I say something regarding the ...
user avatar
0 votes
1 answer
66 views

Does a constant time compression algorithm proves that P=NP?

Supposed someone came up with a compression algorithm that doesn't iterate through bytes or anything to compress data, does that proves P=NP? That is, an algorithm that doesn't rely on patterns/...
user avatar
1 vote
1 answer
33 views

Find the largest subset of unpaired elements [duplicate]

I have a large list (around 200k) of element pairs (e.g. A-B, A-C, B-C, ...). How can I find the largest subset of elements amongst which none are paired? Example ...
user avatar
  • 113
0 votes
1 answer
39 views

Reducing to an NP-complete problem

If $R$ is an arbitrary decision problem that is reducible to $S$, which is an NP-complete problem, what can be said about $R$? I think we should be able to say that $R$ is in NP since an instance of $...
user avatar
1 vote
1 answer
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 ...
user avatar
0 votes
1 answer
27 views

Knapsack with quadratic constraint

Suppose I have a variant of the knapsack problem: $$\max_{x} \sum_{i=1}^n v_ix_i$$ $$(\sum_{i=1}^n w_ix_i - W)^2 \leq k$$ for $v_i, w_i \in \mathbb{R}$, $x_i \in \{0,1\}$ and $k \in \mathbb{R}, k > ...
user avatar
0 votes
0 answers
19 views

Where are some examples of unsatisfiable formulas? Especially about 3CNF paradigm

I've been learning co-NP recently. I know that UNSAT $\in$ co-NP. So I want to find more examples of UNSAT, especially about 3CNF paradigm.
user avatar
  • 153
2 votes
1 answer
57 views

NP-completeness of some problems on assigning candidates to departments

Suppose we have $n$ candidates from a candidate pool $\{1,2, .., n\}$ and we have $m$ departments. A candidate can be assigned to at most one department (so not being assigned is possible). Each ...
user avatar
  • 21
3 votes
1 answer
101 views

4-SAT but two literals per clause must be true

I'm trying to show that a modified 4-SAT in which at least two literals per clause must be true is NP-complete. I'll call it $4_2$-SAT. I understand the reduction from 3-SAT to 4-SAT, and I know why $...
user avatar
1 vote
0 answers
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 ...
user avatar
0 votes
0 answers
45 views

Proving the load balancing problem is NP-Complete

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}...
user avatar
  • 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. ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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. ...
user avatar
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?
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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_{...
user avatar
  • 65
1 vote
1 answer
174 views

Optimal coverage of arbitrary mask by strided masks

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. ...
user avatar
2 votes
2 answers
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 ...
user avatar
  • 123
0 votes
0 answers
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 ...
user avatar
  • 299
0 votes
1 answer
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 ...
user avatar
3 votes
2 answers
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 ...
user avatar
1 vote
0 answers
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 ...
user avatar
  • 183
3 votes
0 answers
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 ...
user avatar
0 votes
1 answer
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 ...
user avatar
  • 151
-2 votes
1 answer
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$?
user avatar
2 votes
1 answer
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 ...
user avatar
1 vote
1 answer
73 views

Why NP-Complete reduction is not reversible?

I have read the question asked here Is polynomial reduction reversible and the logic actually makes sense to me. In other words, if A is polynomially reducible to B, it means that A <= B in terms ...
user avatar
  • 65
0 votes
0 answers
55 views

The problem of packing items into bins? Is it NP-Complete?

I have two arrays. One array represents items. The other array represents bins with capacity. I need to find if all items can be stored in the bins. An item can only be placed in a single bin. But ...
user avatar

1
2 3 4 5
30