Questions tagged [polynomial-time-reductions]
Used in questions asking for efficient (polynomial-time) reductions between computational problems.
13
questions
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
1
vote
0answers
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 ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
1
vote
2answers
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 ...
3
votes
1answer
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 ...
0
votes
1answer
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'$...
2
votes
1answer
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 (...
0
votes
1answer
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 ...
5
votes
1answer
304 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 ...
2
votes
0answers
30 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.
...
