# Questions tagged [polynomial-time-reductions]

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

13 questions
Filter by
Sorted by
Tagged with
15 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 ...
58 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 ...
100 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 ...
16 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 ...
24 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 ...
102 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 ...
145 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 ...
38 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 ...
77 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'$...
39 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 (...
51 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. ...