# Questions tagged [polynomial-time-reductions]

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

137 questions
Filter by
Sorted by
Tagged with
24 views

59 views

### Is finding a Polytime reduction from $L_1$ to $L_2$ equivalent to proving $L_2 \in P \Rightarrow L_1 \in P$

I often hear NP-completeness as problems such that, if they were in $P$ all problems in $NP$ are in $P$. The true definition, though, is that NP-complete is a set of languages in NP that all languages ...
34 views

### Reduction between problems where problem A solves problem B with probability $\frac{2}{3}$

Suppose we have a problem, $A$, and a machine $T_A$ that solves $A$. Now, let's say we have a problem $B$ that is solvable with a polynomial number of calls to $T_A$, and we call $T_B$ the machine ...
96 views

### Does there exist an FPTAS for bin packing problem?

We know that there does not exist an FPTAS for the bin packing problem because it is a strongly NP-HARD problem, as the 3-partitioning problem which is strongly np-hard, can be reduced to the bin ...
29 views

### Partition a family of sets to maximize cumulative overlap and cardinality

My problem is this: I have a list of $n$ items $N$ (think of them as the natural numbers $1,\dots,n$) and $m$ subsets of $N$ $S_1,\dots,S_m$ which may overlap. The objective is to find a partition of ...
32 views

1 vote
39 views

1 vote
175 views

### Show problem is NP-hard

I'm preparing for my exam and I got stuck on the following problem: The gardening problem: We have access to a set of different types of seeds and a number of plant pots.For each plant pot, there is ...
1 vote
31 views

### Choosing the ideal problem to prove the hardness

I am research scholar currently working in complexity theory. Recently, i have started working on hard proofs and reductions. It is very well established that there is a polynomial reduction from ...
31 views

Let $A$ be any unary language. Prove that if $A$ is NP-complete, then P=NP. Approach 1: We just have to prove that we can decide $A$ in polynomial time. Consider a Turing machine that on input $w$, ...
51 views

### I would not be able to get my simulation in my life time

I am running a simulation on my computer. I tried to multiply two polynomials $g(x), h(x)\in GF(2)[x]$, with $degree(g(x))= 8165$, and $degree(h(x))=25$. This multiplication took almost $20$ minutes ...
112 views

75 views

### Given the optimal coloring of a graph how will we find the optimal coloring of its complement graph?

Suppose the optimal color assignment of graph $G$ is given. Does there exist any polynomial-time algorithm that provides the optimal color assignment of its complement graph $\overline{G}$? A ...
298 views

### If you can reduce A to B, does that mean B reduces to A?

If you can reduce A to B, does that mean B reduces to A? Sorry for the stupid question. I think the answer should be yes, because if you can convert all yes-instances of A to yes-instances of B, then ...
118 views

### Prove minimum vertex bisection problem is reducible from bisection width, thereby proving NP-Completeness

The bisection width problem gives you a yes or a no -> if there exists a bisection of size at most $K$ for $G=V,E$. Minimum Vertex Bisection problem gives you a bisection of the smallest size. ...
119 views

### Reduction from vertex-cover to system of quadratic equations

Define $$\text{SQE}=\{S\ |\ S\ \text{is a system of quadratic equations with real solutions}\}$$ and $$\text{VC}=\{G\ |\ G\ \text{is a simple undirected graph with a vertex cover}\ \leq k\}$$ I am ...
32 views

### computation P=L [duplicate]

i have the following question which I'm having some hard time to solve: prove: if every two Languages $A$ and $B$ that have a polynomial reduction ($A$ to $B$) also have a log space reduction ($A$ to ...
1 vote
24 views

### example of an NL-completeness reduction?

I'm looking for simple examples of nondeterministic log-space completeness reductions. In particular I seem unable to construct any nontrivial widget using 2-SAT clauses, which is known to be NL-...
1 vote
65 views