# Questions tagged [polynomial-time-reductions]

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

50 questions
Filter by
Sorted by
Tagged with
27 views

### Polynomial time reducibility is an equivalence relation

How do I prove the following statement? The relation $≤_p$ (polynomial time reduction) is an equivalence relation.
43 views

### If A is not in NP, and A reduces to B, does this mean B is not in NP?

I know it is true that if A is not in P, and A reduces B, then B is not in P. But is it true for NP as well? If A is not in NP, and A reduces to B, does this mean B is not in NP? Why or why not? ...
34 views

### Reduce Subset-Sum to Sat

Is there a reduction from SUBSET-SUM to SAT? Just general SAT, not 3-SAT. Also the given multiset S only has positive integers. SUBSET-SUM is defined as follows: Input: a multiset S = { x1 , ... , xn }...
31 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$ ...
28 views

### Reduction from cardinality constrained project selection problem to CLIQUE problem

Give the polynomial-time $A$ algorithm of the cardinality constrained project selection problem plus the integer k, we are able to compute a maximum-profit set of at most projects to undertake, can we ...
21 views

### Reducing the Hamiltonian Cycle problem to the problem of finding a $m$-length Hamiltonian Cycle

I was working through some exercises regarding NP complexity, when I came across this one: Let $mH$ be the problem of finding a Hamiltonian cycle of length $m$ ($m$ fixed) in a graph $G$. A cycle of ...
22 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. ...
55 views

### What is the polynomial time reduction between these two Hamiltonian cycle problems?

Problem 1: Given an undirected graph, return the edges of a Hamiltonian cycle, or correctly decide that the graph has no such cycle. Problem 2: Given an undirected graph, decide whether or not the ...
23 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{...
429 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-...
40 views

### Converting a Mixed SUBSET-SUM Problem To All-Positive Case

Let's say we have a SUBSET-SUM problem with list {$x_1,x_2,x_3,...x_N$} and weight $W$, with some of $x_i<0$. Is there a known way, in polynomial time, to convert this problem into an equivalent ...
238 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 ...
35 views

### $A \leq_p {\overline{A}} \Leftrightarrow {\overline{A}} \leq_p A$

I want to prove that $$A \leq_p {\overline{A}} \Leftrightarrow {\overline{A}} \leq_p A$$. Does anyone have a Idea how to solve this ?
70 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 ...
22 views

### planar 1-in-3 sat described as a planar graph for independent set

Given a planar 1-in-3 sat formula, can someone reduce that formula into a graph that asks the question when ever there is an independent set for it, that's also planar?
93 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....
11 views

### Does $L \leq_p K$ and $K\in NP$ implies $L \in NP$?

I only find theorems like $L \leq_p K$ and $K\in P$ implies $L \in P$ in books, but I think the same should be true for NP as well. Or is there anything I am missing? I am asking since this would be ...
29 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 ...
52 views

38 views

### Reducing 3-coloring problem to trio representatives

A group of students is divided into trios - groups of 3 members. Each student can be assigned to more than more trio. We want to assign their representatives, by choosing exactly one member of each ...
81 views

### Close To Cook Reduction given NP != coNP

I am struggling to answer these two questions: Prove or wrong: Both are given the assumption that NP != coNP. For any 2 decision problems S, S', if there is a Cook reduction from S' to S then there ...
148 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 ...
178 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. ...
20 views

### Consequences if Exact Cover had a reduction that allowed it to be solved in pseudo-polynomial time?

Here's a pretend example. $S$ = $[9,4,7]$ $C$ = $[[9,4],]$ $f(x)$ = magically encode $x ∈ S$, then $C$ so that the $total~sum~S$ has a value that is $n$^$1000$ Because the value is bounded by ...
24 views

### Will this reduction of Exact Cover into Subset-Sum fail due to a potential false positive?

After removing multi-sets and sets that have elements that don't exist in $S$. $S$ = $[9,6,7,4,5,1,8]$ $C$ =$[[9,6,7],[4,5],[1,8]]$ Transform the values in $C$ of the shared index values with $S$. ...
56 views

### Karp reduction from optimization problems to decision problems

When you consider Cook reductions, then decision and optimization versions of the problems are polynomial time reducible to each other. Focusing on Cook reductions, there exists a natural Karp ...
37 views

### Solving subgraph isomorphism in polynomial time

So I am a bit confused about the reduction between SAT, subgraph isomorphism (SI) and graph isomorphism (GI). I know that GI is in NP, and that SI is NP-complete. So I'm thinking if we can decide ...
73 views

### Is there a language that cannot be polynomially reduced to?

Is there a language A that cannot be polynomially reduced to by some language B? Or is it always possible to reduce a language B to A?
222 views

### Reducing Vertex Cover to Half Vertex Cover

I need to reduce Vertex Cover to Half Vertex Cover using a Karp reduction: Vertex Cover: Given a graph $G = (V,E)$ and an integer $k$, is there a subset of $V$ of size $k$ which intersects all edges? ...
36 views

### Validity of a simple polynomial-time reduction [duplicate]

Let say that P is an NP-hard optimization problem and Q is a problem with unknown complexity. Additionally, we have an algorithm for solving problem Q. We can solve problem P with input x in the ...
51 views

### A non-polynomial reduction

Given two problems $P_1$ and $P_2$. $P_1$ is NP-complete in the strong sense and we want to prove that $P_2$ is also NP-complete but the reduction from $P_1$ to $P_2$ is not polynomial. Can we say ...
27 views

### Find decidable sets such that $A$ reduces to $B$ but not vice versa

I am stuck in this problem, so any help is appreciated. The problem asks to show that there exists decidable sets $A$ and $B$ such that $A \leq_{m}^{p} B$ but $B \not \leq_{m}^{p} A$, and that $A$, $B$...
90 views

### Restriction of SAT to CNF

I have spent a lot of time understanding these two issues. If you can help me, please. Prove that the restriction of SAT to CNF formulas in which each variable xi appears at most twice is solvable in ...
60 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 ...
44 views

### polynomial reduction & co np complete

I would like to know how we can demonstrate these two problems : $A \leqslant_p B$ implies $\overline A \leqslant_p \overline B$ The complement of 3-SAT is co-NP-complete
32 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}$ ...
22 views

### Good NP-complete reduction candidates for disjoint bilinear programs

Given a disjoint bilinear programm $max\{x^TQy: x \in X, y\in Y\}$, with $Q$ being a matrix and $X$ and $Y$ specific polytops (i.e. like X = knapsack polytop or Y = stable set polytop) What are some ...
65 views

### If any problem in NP is not in P then NP C ∩ P = ∅

If any problem in NP is not in P then NPC ∩ P = ∅ The proof is: We have $X ∈ NP$ and $X \not\in P$. Assume $Y ∈ NP C ∩ P$. As $X ≤_P Y$ we have $X ∈ P$, which is a contradiction. I have not clear ...
1k views

### Reduction from Vertex Cover to Dominating Set

I am trying to reduce the vertex cover (decision) problem to the dominating set (decision) problem in order to prove that the latter is NP-hard. After some research online, I found that many articles ...
36 views

### What are the requirements for a superset of P to be closed under karp reductions?

So today in our exercise session on complexity theory we discussed that P, NP, and BPP are closed under karp reduction. We also figured that the proofs could likely be expanded to straight ...
30 views

### If $Q$ reduces to $L$ then $\overline{Q}$ reduces to $\overline{L}$

The following exercise is taken from Chapter 17 of Languages and Machines by Thomas Sudkamp: Let $Q$ be a language reducible to a language $L$ in polynomial time. Prove that $\overline{Q}$ is ...
196 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 ...
346 views

### P/NP - Polynomial Reduction vs Certificate

I am learning about the P/NP problem right now, and I don't understand when to use polynomial reduction and when to use a certificate. How I understand polynomial reduction is that you can use it to ...
43 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 ...
87 views

### Are every problems in EXP karp reducible to any EXP-Complete?

According to wikipedia and other references there exists complete language $L \in EXP$ such that for every languages $L'$ in $EXP$ there exists a polynomial reduction $f$ that converts instance of $L'$...
115 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 (...
111 views

### weighted-clique to vertex cover reduction

WEIGHTED-CLIQUE input: a undirected graph G that has weighted edges and 2 natural numbers a, b question: does G have a clique of size a with total weight of b? I want to prove that this ...
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 ...
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. ...