The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Questions tagged [polynomial-time-reductions]

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

Filter by
Sorted by
Tagged with
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. ...