Questions tagged [polynomial-time-reductions]
Used in questions asking for efficient (polynomial-time) reductions between computational problems.
8
questions
1
vote
1answer
70 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
48 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
36 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
72 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
33 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
40 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 ...
3
votes
1answer
63 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
26 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.
...
