Questions tagged [polynomial-time-reductions]
Used in questions asking for efficient (polynomial-time) reductions between computational problems.
6
questions
1
vote
0answers
20 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
53 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
37 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 ...
2
votes
1answer
52 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
25 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.
...
