Skip to main content
Share Your Experience: Take the 2024 Developer Survey

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
1 vote
1 answer
374 views

If coNP ⊆ NP, does that mean coNP = NP?

I had an exam, and one of the questions was Does ZPP = BPP if coNP ⊆ ZPP. I came down to coNP ⊆ NP and went on with "then coNP = NP", am i right?
Naneless's user avatar
1 vote
0 answers
70 views

Constructing simple polygon from non-crossing orthogonal line segments

Given a set of $N$ non-crossing orthogonal (vertical and horizontal) line segments on the plane, is there an efficient algorithm to construct a simple orthogonal polygon that passes through all given ...
Mohammad Al-Turkistany's user avatar
1 vote
0 answers
28 views

NP-hardness of subset sum of multiple supersets

Given the following problem: Input: A set of disjoint sets $s_1, s_2, \dots s_n$, and an integer $K$ Question: Is there a set A with $|A|= n$ and $|s_i \cap A| = 1$ for all i from 1 to n, s.t. $\sum_{...
SimonNW's user avatar
  • 86
1 vote
1 answer
42 views

Graph Coloring Decision Problem Reduction to Prove NP-Complete

I am doing research into NP-Complete problems and more specifically started looking into the Graph Coloring Decision Problem or the k-Coloring problem, as described here: Given a graph $G = (V, E)$ ...
Darien's user avatar
  • 11
1 vote
1 answer
45 views

Proving that the shortest simple path problem between two vertices 𝑠 and 𝑡 in a graph with given path upperbound be positive is NP-complete

This is the same problem here but with one more condition that the sum of the distance cannot be a negative integer. The full description of the problem is: Is it possible to find a simple path (no ...
Lebecca's user avatar
  • 113
2 votes
0 answers
31 views

Satisfiability of a boolean formula with two occurrences of each variable with a special ordering

I am interested in the complexity of a special case of the boolean satisfiability problem: We are given a boolean formula, consisting only of the logical operators $\land$ and $\lor$ (that can be ...
SimonNW's user avatar
  • 86
-1 votes
1 answer
25 views

Show that it is Np-hard to determine whether a given graph has the crossing number k

I want to prove that this problem to find whether the crossing number of any given graph is K or not, is NP-Hard. I don't know how to do this. Can someone help me with this ?
Virar's user avatar
  • 1
0 votes
1 answer
42 views

If $P=NP$, then $LCP \in P$

I want to prove that if we assume $P=NP$, then we can find the longest cycle (maximal number of vertices, no repeated edges, only repeated vertex is the starting one) in an undirected graph in ...
Dave the Sid's user avatar
0 votes
0 answers
16 views

Kernelization For Odd Cycle Transversal Problem on Perfect Graphs

This problem appears as exercise 2.33 in https://www.mimuw.edu.pl/~malcin/book/parameterized-algorithms.pdf (page 48). A perfect graph $G$ is bipartite if and only if it contains no triangle graphs. ...
Yavuz Bozkurt's user avatar
-2 votes
1 answer
27 views

How do you show that Cosmic Kite Problem is NP complete?

A "cosmic kite" of size k consists of a clique of k nodes with a path of k nodes that unfolds from one of the nodes in the clique. Cosmic Kite as decision problem Input: a graph G = (V, E) ...
Nicolò Bonacorsi's user avatar
6 votes
1 answer
959 views

Why is 3-SAT used for proving NP-Completeness so often?

I was wondering why 3-SAT is often chosen as the candidate problem from which one reduces from to prove the NP-completeness of another algorithm. I've seen it justified in places such as K&T by ...
entangled_photon's user avatar
1 vote
1 answer
36 views

Polynomial-Time Solvability Through NP-Completeness Reductions

Let A and B be NP-complete problems. Suppose I have established reductions from problem A to problem B and vice versa. Now, considering a specific instance (or set of instances) of problem A that can ...
Lewis Trem's user avatar
1 vote
1 answer
114 views

Prove "Vertex Cover OR Clique" is NP complete

Instance: An undirected graph $G$ and a positive integer $k$ Question: Does $G$ contain a vertex cover of size $\leq k$ or a clique of size $\geq k$? Obviously, this problem is solved by polynomial ...
Hugh Mann's user avatar
-2 votes
2 answers
77 views

Quasi polynomial algorithm for np complete problem

I know that quasi polynomial algorithm is neither polynomial nor exponential. But I want to know if we find such algorithm for NP complete problem, will it be of any use? Or is there such algorithm ...
user's user avatar
  • 11
0 votes
0 answers
35 views

If this variant of Subset Product remains NP-complete, what other inputs could give me exponential time?

Given $N$ a whole number and a set $S$ of divisors of N, where no repetition is allowed. Decide if there is a combination of divisors with a product equal to $N$. Remove non-divisors from $S$. Remove ...
The T's user avatar
  • 321
3 votes
1 answer
71 views

Maximum Vertex Set With a Minimum Pairwise Distance Requirement in Directed Acyclic Graphs

Let $G=(V,E)$ be an unweighted directed acyclic graph with a set $V$ of vertices and a set $E$ of edges. The all-pairs shortest path problem can be solved efficiently using the Floyd-Warshall ...
Daniel García's user avatar
1 vote
1 answer
52 views

Does the Subset Product Problem remain NP-complete if repetition in S is not allowed?

Just curioius, I wanted to know when $S$ ={set of divisors of N} and we're given $N$ a target product. Our goal is to decide if a combination in $S$ has product equal to N. Does the problem remain NP-...
The T's user avatar
  • 321
0 votes
1 answer
28 views

Is every problem which can be solved by an algorithm using polynomial space in PSPACE?

I recently learned about the definition of PSPACE problems, which are a subset of decision problems that can be solved by using polynomial space. However, one thing I don't understand is when I asked ...
Dang Quang Vinh's user avatar
10 votes
4 answers
3k views

Are there languages L1 ⊆ L2 ⊆ L3 when L1 and L3 are NP-Complete languages and L2 ∈ P?

Are there languages L1 ⊆ L2 ⊆ L3 where L1 and L3 are NP-Complete languages and L2 ∈ P? Would this imply P=NP? Thanks
Avi Tal's user avatar
  • 339
0 votes
0 answers
30 views

Is this version of SAT NP-Complete?

Given a SAT instance such that: Each clause is of length at most 4. Negative literal occurs only in clauses of length=2. Each length 2 clause has at most 1 negative literal. Is this version of SAT ...
TheoryQuest1's user avatar
0 votes
0 answers
38 views

Show 3-colorable graph with hamiltonian cycle is NP-Complete

The language is : $3COLORHC = \{<G> | \text{ G is an undirected 3-colorable graph that contains Hamiltonian cycle} \}$ I was asked to show that this language is NP-Complete. Showing that the ...
Yarin's user avatar
  • 275
1 vote
1 answer
82 views

Is this intersection set problem NP-Hard?

Suppose we have collection of n sets $S_1, S_2, \dots, S_n$. Each set has a size of at least $k$. We know for sure that $\exists k$ sets where all of them contain the same $k$ elements; $|S_1 \cap S_2 ...
Xfae's user avatar
  • 13
2 votes
1 answer
60 views

Decide whether this Problem NPC or P?

Input: A finite set A, subsets S1, . . . , Sn ⊆ A, and a number k ∈ N. Question: Does there exist a set R ⊆ A with |R| = k such that |R ∩ Si| = |Si| for all 1 ≤ i ≤ n? I read somewhere (without ...
Arugo's user avatar
  • 49
0 votes
1 answer
34 views

Knapsack Problem for Fixed weight and Fixed price

Is the knapsack problem for a target weight, let's say 1000 for example, and a target price, let's say 10000, still an NPC problem?
Arugo's user avatar
  • 49
3 votes
2 answers
132 views

Proof that $NP \cap coNP = P$

Suppose I want to prove that $NP \cap coNP = P$. Since clearly $P\subseteq NP \cap coNP$, I need to prove the opposite direction, i.e., every problem in $NP \cap coNP$ has a polynomial-time algorithm. ...
Erel Segal-Halevi's user avatar
0 votes
0 answers
20 views

Proof Closer String/Consensus String/Center String is NP-hard

Given are n gene sequences (words over the alphabet {A, T, C, G}), each of length m. Find a gene sequence (of length m) that minimizes the maximum distance to all given gene sequences. Here, distance ...
shinichi's user avatar
1 vote
0 answers
51 views

Is it known, whether the complement of NP-hard problems is necessarily again NP-hard?

Neither could I find any counterexamples, nor could I show that if indeed the complement of NP-hard problems was NP-hard, one could deduce some unknown results from it, which would imply that it is ...
LostBetweenTheLines's user avatar
3 votes
1 answer
134 views

Is this an example of a natural, strictly NP-intermediate language (assuming EXP ≠ NEXP)?

In the wikipedia page for the NP-intermediate complexity class, the following observation is made: Under the assumption that P ≠ NP, Ladner explicitly constructs a problem in NPI, although this ...
Federico's user avatar
2 votes
0 answers
31 views

How can the approximation algorithm of one NP-complete problem be used to prove "the class P would be the same as the class NP"?

Recently, when I self-learnt Discrete Mathematics and Its Applications 8th by Kenneth Rosen, I had some questions about some statements in it. Fur- thermore, if a polynomial worst-case time ...
An5Drama's user avatar
  • 203
1 vote
1 answer
64 views

Subset ${\tt XOR}$ problem

Motivation. This is a variant of the subset sum problem involving the bitwise ${\tt XOR}$ operation. Problem. Given a set $X$ of $n$ bit-strings of length $n$, determine if there is a non-empty subset ...
Dominic van der Zypen's user avatar
2 votes
1 answer
76 views

Proof that the K coloring problem is weakly or strong NP-complete?

As far as I know, the K coloring problem is NP-complete. However, I'm a bit confused about how to determine whether a problem is weakly or strongly NP-complete. If an NP-complete problem is decidable ...
wellknow's user avatar
3 votes
0 answers
39 views

Approximation of the Normal Set Basis Problem

Let $B$ and $C$ be collections of finite sets. We say that $B$ is a normal basis of $C$ if for all $c\in C$ there is a pairwise disjoint subcollection of $B$ whose union is exactly $c$. The input of ...
Bader Abu Radi's user avatar
2 votes
1 answer
113 views

Problem about $NP \neq coNP$

I need to show that assuming $NP \neq coNP$ then there are 2 non-trivial languages $A$ and $B$ ($A,B \neq \emptyset, \Sigma^*$) in $NP \cup coNP$ such that there's no polynomial time reduction from A ...
Yarin's user avatar
  • 275
1 vote
1 answer
74 views

Reduction from dominating set to disconnected dominating set

Consider an undirected graph $G = \langle V, E\rangle$, and a set $S\subseteq V$ of vertices. We say that $S$ is a dominating set, if for every vertex $v\in V$, it holds that $v\in S$, or $v$ has a ...
Zumikya's user avatar
  • 73
0 votes
1 answer
90 views

Double Dominating Set NP-Complete

How do i show that Double Dominanting Set is NP-Complete by reducing Dominating Set to it i have thought by adding a edge but my solution is not correct Input is an undirected graph and a target. The ...
user avatar
3 votes
1 answer
358 views

What do we know about the asymptotic proportion of "easy" instances of NP-complete problems

In practice, it seems that many NP-hard problems "usually" lead to easy instances, in the sense that a commercial solver can handle them reasonably. A few past questions on this topic (see ...
Davis Yoshida's user avatar
2 votes
2 answers
360 views

Algorithm that generates verification program from solution program of NP problem

I don't know complexity class theory well so I might make some categorical errors, but I will try to ask this question anyways. Suppose you have written a function in some programming language which ...
Robert Wegner's user avatar
2 votes
0 answers
118 views

Finding highest value/weight ratio in dependency graph: NP-hard?

I have the following problem, and would like to figure out whether or not it's NP-hard - primarily to know that searching for a polynomial algorithm for it is futile. Approximations are possible, and ...
Pieter Wuille's user avatar
0 votes
0 answers
25 views

Computational Learning Problem: 3-DNF Reduction

I'm not sure how to solve this problem. Problem statement is: Consider the binary classification problem where X = R d and Y = {0, 1}. Consider the class of Binary classifiers given by intersection of ...
Mr.Zhang's user avatar
0 votes
0 answers
30 views

Which one of the problems belong to P? [duplicate]

Suppose $P\neq NP$. The following problem can be solved in polynomial time? Given natural number $n$ and positive real numbers $a_1,a_2,\dots,a_n$ and $b_1,b_2,\dots,b_n$. The goal is to find $I\...
ErroR's user avatar
  • 1,942
3 votes
0 answers
47 views

Variant of Bounded Subset Product

Consider the following decision problem: Given $([b_1, \cdots, b_n],t)$, where $[b_1, \cdots b_n]$ is an array of natural numbers each less than $n^c$ and $t$ is a target natural number, do there ...
adelta's user avatar
  • 31
1 vote
0 answers
51 views

Complexity of topological sorting with a special restriction

Let $G = (V, E)$ be a connected DAG (representing a circuit) with every vertex may be one of the following three types: Input variable, with in-degree $0$ and out-degree $\geqslant 1$. A gate, with ...
user779130's user avatar
1 vote
2 answers
115 views

NP-hardness of modified distance-colouring of graphs

Given a graph $G =(V,E)$, a set of colors $\mathcal{C}=\{0,1,2,3,...,c-1\}$, and an integer $r$, I want to know if I can find a coloring procedure that can assign a color to each nodes (all nodes must ...
r236's user avatar
  • 11
0 votes
0 answers
34 views

An Example of the Conjuction of Two NP-Complete Decision Problems Being Polynomial Time Solvable [duplicate]

Firstly, we define A and B as two decision problems with the same set of inputs. Define a new decision problem "A AND B" as follows: The input to "A AND B" is any valid input x for ...
Oluchi A's user avatar
0 votes
1 answer
62 views

3 Processor Scheduling

A set of n independent tasks, each having integer execution times, are to be executed using three identical processors. A task can be executed in any of the three processors. Develop a sequential ...
Sachin's user avatar
  • 1
2 votes
1 answer
61 views

Subset sum reducible to barter economy problem?

I was given the following problem called the barter economy problem: Given a set of $n$ people $\{p_1, \ldots, p_n\}$ and a set of $m$ distinct objects $\{a_1, \ldots, a_m\}$, where each object $a_j$ ...
redbull_nowings's user avatar
0 votes
2 answers
176 views

( Soft question ) P vs NP - is such a situation possible?

Currently P vs NP is the holy grail of theoretical computer science. And the nature of the problem is as such that if actually P = NP is proved then most of the proofs for mathematical statements ...
Aditya Mishra's user avatar
1 vote
1 answer
93 views

Is there an efficient algorithm for this ecommerce optimization problem?

Consider the problem of minimizing the checkout price of a shopping basket in the presence of some discount rules: There are $n \gt 0$ distinct products in our shopping basket. Each product is ...
Jo Ma's user avatar
  • 15
1 vote
1 answer
65 views

Maximum Weighted coverage approximation algorithm?

I am looking for an algorithm similar to the unweighted maximum coverage. However, I have been unable to find a similar algorithm for the weighted version. How should I modify the algorithm above to ...
calveeen's user avatar
  • 141
1 vote
1 answer
61 views

Is this variant of multiset covering problem NP-hard?

Consider this variant of multiset covering problem. Input: a collection of sets $S = \{s_1, s_2, \ldots, s_n\}$ and a universal set $U$, in which $s_k \subseteq U$ and $s_k \neq \emptyset$ for all $k$...
Josh's user avatar
  • 11

1
2 3 4 5
33