Skip to main content

Questions tagged [polynomial-time-reductions]

Used in questions asking for efficient (polynomial-time) reductions between computational problems.

Filter by
Sorted by
Tagged with
8 votes
2 answers
587 views

NP-hardness for one-dimensional facility location problem with entrance fee for each customer

We have $n$ customers, $(x_1, \dots, x_n)$, sorted on the read line. For convenience, we also use $x_i$ to denote its coordinate on the line. We need to locate $m$ facilities on the real line. We note ...
asdfqwer's user avatar
6 votes
1 answer
147 views

Is there such a notion as "effectively computable reductions" or would this be not useful

Most reductions for NP-hardness proofs I encountered are effective in the sense that given an instance of our hard problem, they give a polynomial time algorithm for our problem under question by ...
StefanH's user avatar
  • 1,449
6 votes
1 answer
5k views

vertex cover reduction to subset sum

Subset sum Input: A multi set $S$ of numbers and a natural number $t$ Question: Does $S$ contain a subset $A$ such that $\sum_{x \in A} x = t$? (e.g., $\{1,1,2,3,4,5\}$, by multiset it ...
sam's user avatar
  • 61
4 votes
1 answer
801 views

Proofs of reduction of any hard problem

Approach:1 To prove any unknown problem $B$ is NPH then take any known NPH problem $A$ (e.g. $3$-sat) which reduces to $R$ in polynomial time. If I take any instance example $I_1$ of $A$, then ...
S. M.'s user avatar
  • 327
4 votes
1 answer
215 views

Showing the language of all graphs that are both 4-colorable and not 3-colorable is coNP-hard

As the title states, I need to prove that the language of all graphs that are both 4-colorable and not 3-colorable is coNP-hard. I'm not looking for a solution but a clue or something to help me ...
OE.omergunr100's user avatar
4 votes
1 answer
2k views

Prove finding k disjoint paths from n given paths in a directed graph is NP-complete

Problem: Given n paths in a directed graph G(V, E) and an integer k, find out k paths among them such that no two of them pass through a common node. Prove that the given problem is in NP-complete. ...
user avatar
4 votes
1 answer
3k views

CLIQUE $\leq_p$ SAT

i'm trying to reduce CLIQUE to SAT: Given: Graph G=(Vertices V, Edges E) and $k \in \mathbb{N}$ Output: Formular F such that if G contains a complete subgraph of size k, the formular is satisfiable (...
gxor's user avatar
  • 185
4 votes
1 answer
138 views

Complexity of a decision problem: system of linear equations over finite field with restricted solutions

I have a system of linear equations over a finite field $\mathbb F_p \cong \mathbb Z_p$, and I'm interested in the decision problem of whether there exists a solution where all of the variables $x_i$ ...
Peter Kagey's user avatar
4 votes
0 answers
38 views

Cardinalities in set coverings

Let $I$ be a set of items; $C \subseteq \mathcal{P}(I)$ be a set of subsets of $I$, where $\mathcal{P}(I)$ stands for the power set of $I$; And $C(i) = \{ c \in C \mid i \in c \}$ be the set of sets, ...
Matheus Diógenes Andrade's user avatar
3 votes
3 answers
2k views

Easy proof for $Primes \in NP$

I want to show that $Primes \in NP$ an I've seen multiple proofs that use facts from number theory, like this one. But isn't it much easier to proof $$Composites=\{x\in \mathbb{N}\cup\{0\}:x=1 \vee\...
Quotenbanane's user avatar
3 votes
1 answer
97 views

Given the optimal coloring of a graph how will we find the optimal coloring of its complement graph?

Suppose the optimal color assignment of graph $G$ is given. Does there exist any polynomial-time algorithm that provides the optimal color assignment of its complement graph $\overline{G}$? A ...
Subhankar Ghosal's user avatar
3 votes
2 answers
164 views

Interpretation of co-NPCompleteness?

Given a Problem $A$ that has an answer $true$ if and only if both conditions $1$ and $2$ are $false$, for some conditions 1 and 2. Whether condition $2$ is $true$ can be tested with certainty in ...
J.Doe's user avatar
  • 789
3 votes
1 answer
100 views

Is there a book with 100 reductions?

In a lecture I'm taking about complexity theory a professor said, there are infinite many NP-complete problems. Question: I was wondering if there exists something like a database or a book with some ...
Algebruh's user avatar
  • 321
3 votes
1 answer
57 views

Why can KARP reductions be used to define completeness for complexity classes in the polynomial hierachy?

When defining $\Sigma_i^P$ or $\Pi_i^P$ completeness, we want to use a reduction that fulfills the following property: If $L' \leq_p L$ and $L \in \Sigma_i^P$ or $\Pi_i^P$ respectively, then $L'$ is ...
csstundent's user avatar
3 votes
1 answer
63 views

EXP reduction to show NEXP-completeness

I wonder why can't I allow an exponential-time reduction from all problems in $\textbf{NEXP}$ to a language $L$ and claim $L$ to be $\text{NEXP-complete}$. The computational complexity class $\text{...
Zee's user avatar
  • 243
3 votes
1 answer
205 views

NP completeness of deciding whether a set of examples, consisting of strings and states, has a corresponding DFA?

I'm working on a textbook problem, 7.36 in Sipser 3rd edition. It claims that if we are given an integer $N$ and set of pairs $(s_i, q_i)$, where $s_i$ are binary strings and $q_i$ are states (we are ...
xdavidliu's user avatar
  • 858
3 votes
0 answers
592 views

Is there any polytime reduction from feedback vertex set to vertex cover?

I know that feedback vertex set (FVS) problem is $\mathrm{NP}$-complete since there is a simple and nice polytime reduction from vertex cover (VC) problem to FVS. Specifically, given a undirected ...
Blanco's user avatar
  • 623
3 votes
0 answers
87 views

Multipoint evaluation of a given polynomial

You are given a polynomial of degree n. We have to find the value of the polynomial at n different points in O(n(log(n))^2). The answer should be modulo 998244353. I have read various blogs on it and ...
Abhijeet Narang's user avatar
2 votes
2 answers
599 views

Definition of NP-hardness for non-decision problems

As I understand, the term "NP-hardness" is applicable when we also talk about optimization or search problems (i.e. return the satisfying assignment for 3-SAT). How do we formally define NP-...
user avatar
2 votes
1 answer
254 views

SAT satisfaction with 10 variables

I am trying to prove that the next problem is NPC: $$ A = \{ \langle\phi\rangle \ \big| \ \phi \ \text{is CNF and has sat. assignment where exactly 10 vars are TRUE} \} $$ I am trying to find ...
Ella 's user avatar
  • 109
2 votes
1 answer
465 views

Why is Independent Set "at least" and Vertex Cover "at most" k

The decision version of the Independent Set and Vertex Cover problems are phrased as: Given a graph G and a number k, does G contain an independent set of size at least k? Given a graph G and a ...
nicetyartwork's user avatar
2 votes
1 answer
64 views

Is finding a Polytime reduction from $L_1$ to $L_2$ equivalent to proving $L_2 \in P \Rightarrow L_1 \in P$

I often hear NP-completeness as problems such that, if they were in $P$ all problems in $NP$ are in $P$. The true definition, though, is that NP-complete is a set of languages in NP that all languages ...
Ank i zle's user avatar
  • 153
2 votes
1 answer
120 views

Maximum independent subset for graphs with lots of edges

Consider an NP-hard graph problem, like the maximum independent set problem. Let us say I restrict my inputs to only be graphs that have $n$ vertices and at least $n^{c}$ edges, for some $c > 1$. ...
Sid Meier's user avatar
  • 249
2 votes
1 answer
778 views

Using FFT as a black box to solve subset sum. How is this done? Given a set of numbers, S, and a target value T

Given a set of numbers, S {s1, s2, ... sn} and a value T, I am looking to determine if any three elements in the set add up to value T. It is valid to have repeats like 2+2+2 would be fine for ...
joelsh's user avatar
  • 21
2 votes
2 answers
193 views

Solving Exact2IS using IS

i encountered the following problem: Exact2IS ={G has exactly 2 independent sets} Assuming that given a graph G i can find an independent set how can i check if G has exactly 2 independent sets. (i ...
user avatar
2 votes
1 answer
123 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
2 votes
1 answer
121 views

How to provide a reduction from 3SAT to domatic number problem

How to provide a reduction from 3SAT to domatic number problem. Domatic number problem: Given a graph $G = (V, E)$ and an integer $k$, can we partition $V $ into at least k disjoint sets of vertices, ...
Hughson's user avatar
  • 21
2 votes
1 answer
211 views

Reduction from vertex-cover to system of quadratic equations

Define $$\text{SQE}=\{S\ |\ S\ \text{is a system of quadratic equations with real solutions}\}$$ and $$\text{VC}=\{G\ |\ G\ \text{is a simple undirected graph with a vertex cover}\ \leq k\}$$ I am ...
Tom Finet's user avatar
  • 258
2 votes
1 answer
42 views

Partition a family of sets to maximize cumulative overlap and cardinality

My problem is this: I have a list of $n$ items $N$ (think of them as the natural numbers $1,\dots,n$) and $m$ subsets of $N$ $S_1,\dots,S_m$ which may overlap. The objective is to find a partition of ...
Jonas Juul Hansen's user avatar
2 votes
1 answer
18 views

Question on worst-to-average-case reductions

Consider two decision problems A and B. We know that A reduces to B in polynomial time --- if we could solve B, we have a procedure to solve A. Now, let's say it is known that the worst case instances ...
BabyBlue's user avatar
  • 123
2 votes
2 answers
344 views

Problem reduction: Can YES-Instances also be mapped to NO-Instances if there is perfect correspondence?

Definition: Problem A is reducible to problem B if an algorithm for solving problem B efficiently (if it existed) could also be used as a subroutine to solve problem A efficiently. When this is true, ...
NoteMyQuestion's user avatar
2 votes
2 answers
885 views

Proving NP-hardness of Hamiltonian Cycle problem variant

I need to prove that determining whether a graph has a relaxed-Hamiltonian cycle (definition given ahead) is NP-hard. A relaxed-Hamiltonian cycle in $G$ is a closed walk $C$ that visits every vertex ...
Dhruv Deshmukh's user avatar
2 votes
1 answer
197 views

$k$-SAT completeness proof when $k$ is linear in number of variables

I'm looking at a special version of SAT in which each clause has exactly $n/2$ literals, where $n$ is the number of variables. Can we prove NP-completeness of SAT in this case? I tried reducing 3-SAT ...
dda's user avatar
  • 21
2 votes
0 answers
80 views

Limited number of calling for a decision blackbox to compute all the solutions

I am trying to reduce between a solution problem and a decision version of the same problem. The problem is the orthogonality problem. Given $2$ sets $L$ and $R$, whose size each is $n$ vectors over $\...
Dan D-man's user avatar
  • 524
2 votes
0 answers
114 views

A polynomial time reduction and the size of problem (exact cover)

An exact cover problem is one of the NP-complete problems. Given a family $\mathbb{I}$ of subsets of a set $[n]=\{1,\dotsc,n\}$, whether there exists a subfamily $\mathbb{I}'\subseteq \mathbb{I}$ ...
Sanghack Lee's user avatar
2 votes
0 answers
262 views

NP-completeness of Induced disjoint paths between a set of sources and a set of sinks

In a given undirected graph $G(V,E)$, a set of $k$ paths is said to be induced if: They are vertex-disjoint. Each one is itself an induced path. No edge connects two vertices of two different paths. ...
Thinh D. Nguyen's user avatar
1 vote
3 answers
244 views

Spanning tree whose sum of edge weights are between two boundries

I saw this problem: $\langle G,w,k_1,k_2 \rangle \in L$ iff Graph $G$ has a spanning tree whose sum of edge wights are less than $k_2$ and greater than $k_1$. The problem says that we can prove this ...
Omid Yaghoubi's user avatar
1 vote
1 answer
595 views

Concrete example of Vertex Cover to Subset Sum reduction

In Computational Intractability, we often come across a need to reduce Vertex Cover (VC) problem to a Subset Sum problem, mostly to prove Subset Sum is NP-Complete. I also see a reduction in the line ...
KGhatak's user avatar
  • 229
1 vote
1 answer
78 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
1 vote
1 answer
81 views

Bipartite matching with constraints on one part

We have a bipartite graph with parts $A$ and $B$, and it is edge weighted. We have some constraints for part $B$. Each constraint is in this format: Between vertices $b_1$ and $b_2$ both from part $B$,...
Soroush Vahidi's user avatar
1 vote
1 answer
802 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....
Pepe's user avatar
  • 165
1 vote
1 answer
121 views

How to construct complement of NFA universality?

Given an input NFA, can one construct an NFA that is universal (that is, accepts all its inputs) if and only if, the input NFA isn't universal? I tried to use the fact that NFA-universality is PSPACE-...
NooneAtAll3's user avatar
1 vote
1 answer
36 views

Choosing the ideal problem to prove the hardness

I am research scholar currently working in complexity theory. Recently, i have started working on hard proofs and reductions. It is very well established that there is a polynomial reduction from ...
Balchandar Reddy's user avatar
1 vote
1 answer
941 views

If every NP-hard language is PSPACE-hard then NP=PSPACE

To prove PSAPCE = NP we will show following inclusions : NP $\subseteq$ PSPACE : If every NP-hard language is PSPACE-hard then SAT is also PSPACE-hard. Since every language in PSPACE can be reduced ...
False Equivalence's user avatar
1 vote
1 answer
146 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 ...
Francis's user avatar
  • 65
1 vote
1 answer
267 views

Show that a problem about permutations is NP-Complete

I want to prove that the following problem is NP-Complete. Input: Set $S = \{s_1, \dots, s_n \}$, set $T \subset S \times S$, that contains ordered pairs $(s_i, s_j) : s_i \neq s_j$, and an integer $...
entechnic's user avatar
  • 143
1 vote
2 answers
230 views

What's wrong with the reduction from integer programming to linear programming?

I'm confused with polynomial-time reduction and NP-hardness. Let's say that the following integer programming is NP-hard. $\min_{x \in K} f(x)$, where $K$ is a finite subset of $\mathbb{N}$. But it is ...
nemy's user avatar
  • 113
1 vote
1 answer
91 views

polynomial reduction within Np

If $A \le_p B$ and $B\in NP$, does it necessarily follow that $A\in NP$? ($\le_p$ is a polynomial many-one reduction) A quick yes/no comment is enough, a proof would be nice :-)
Jonas De Schouwer's user avatar
1 vote
1 answer
20 views

Assuming the original instance is not easy in NP-hardness reduction

Partition problem: given a non-empty finite set $P = \{p_i : i ∈ I = \{1,\dots,m\}\}$ of $m$ positive integers such that $\sum_{i=1}^m p_i = 2T$, can $I$ be partition into two disjoint subsets $I_1, ...
Anton's user avatar
  • 11
1 vote
1 answer
215 views

If a language consists of an NP and coNP question, do we have to place it in P^NP^NP?

If $x \in L$ only if $x \in A$ and $x \in B$, where A is an NP problem and B is a coNP problem, I cannot place $L \in NP$ or $L \in coNP$ without implying that NP = coNP right?
Friedrich's user avatar